Background

In Hakugyokurou, the concert in the Netherworld has begun.

Lunasa, Lyrica, and Merlin are performing.

Problem Description

Kochiya Sanae really likes the performance of the Ghost Band, and she wants to score their performance.

Since the Ghost Band has $3$ members, we can use three positive integers $A,B,C$ to represent the score of the band’s performance. Their performance score can be written as

$$\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C}\left(\frac{\text{lcm}(i,j)}{\gcd(i,k)}\right)^{f(type)}$$

Because the music sounds different in different parts, $type$ changes within $\{0,1,2\}$, where:

$$\begin{aligned} f(0)&=1 \cr f(1)&=i \times j \times k \cr f(2)&=\gcd(i,j,k) \end{aligned}$$

Because the band’s songs are so good that the score becomes very large, the score should be taken modulo a given positive integer $p$.

Since there are many songs to perform, Sanae gives $T$ queries.

Input Format

The first line contains two positive integers $T$ and $p$, as described above.

The next $T$ lines each contain three positive integers $A,B,C$, representing one query.

Output Format

Output $T$ lines. Each line contains three positive integers, representing the value of the given expression when $type=0/1/2$, respectively.

3 998244853
1 1 1
2 2 2
3 3 3

1 1 1
16 4096 16
180292630 873575259 180292630

Hint

Constraints and Notes

For $10\%$ of the testdata:

$$1\leq A,B,C\leq 50$$

For $20\%$ of the testdata:

$$1\leq A,B,C\leq 100$$

Another $10\%$ of the testdata:

$$1\leq A,B,C\leq 100\ \ \ \ \ A=B=C$$

For $60\%$ of the testdata:

$$1\leq A,B,C\leq 10^3$$

For $100\%$ of the testdata:

$$1\leq A,B,C\leq 10^5 \ \ \ \ 10^7 \leq p \leq 1.05\times 10^9\ \ \ \ p\in \{ prime\} \ \ \ \ T =70$$

---

Sanae is very kind. Even if you do not know all the correct answers, she will still give you some points.

• If your first column is correct, she will give you $20\%$ of the score for this test point.
• If your second column is correct, she will give you $40\%$ of the score for this test point.
• If your third column is correct, she will give you $40\%$ of the score for this test point.

So even if you do not know what the answers are, please output an integer in $[0,2^{31})$ for the parts you do not know, otherwise it may cause unpredictable errors.

Source

Lost House 2019 League (MtOI2019) T5.

Problem setter: CYJian.

Translated by ChatGPT 5