Background

Little Z is a very inexperienced OIer.

Little Z has no idea how to create a problem, and with only one day left before the submission deadline, he still has no ideas.

Therefore, he chose a very simple problem, hoping that everyone participating in the contest can achieve a perfect score of $100$ on this problem.

Description

Little Z likes numbers. He came up with the following game:

Little Z has $n$ numbers $x_1, \dots, x_n$. Before the game starts (at time $0$), all these numbers are $0$.

Little Z has a random number generator that produces integers in the range $[1, n]$. This generator has $n$ positive integer parameters $v_1, \dots, v_n$. Let $p_i = \frac{v_i}{\sum_{j=1}^n v_j}$. When it generates a random number, the probability of generating $1$ is $p_1$, ..., the probability of generating $x$ is $p_x$, ..., and the probability of generating $n$ is $p_n$.

Little Z also has $n$ positive integers $l_i > 1$, where the $i$-th number $l_i$ means that all operations on $x_i$ are performed modulo $l_i$.

In the game, Little Z performs the following operations sequentially at each time step:

1. Use the random number generator to produce an integer. Let the generated integer be $k$. Little Z increments the $k$-th number by one and performs the modulo operation. That is, $x_k \leftarrow (x_k + 1) \bmod l_k$.
2. Record the current sequence of all numbers $(x_1, x_2, \dots, x_n)$ on a piece of paper. The paper can be considered to have infinite length.

When Little Z records the all-zero sequence $(0, 0, \dots, 0)$ at some time step, he realizes that all numbers have returned to their initial state, and he ends the game.

Little Z does not care about the duration of the game; he wants to know how many different sequences $(x_1, x_2, \dots, x_n)$ will appear on the paper. Therefore, he wants to find the expected number of distinct sequences $(x_1, x_2, \dots, x_n)$ on the paper when the game ends.

Little Z cannot solve this problem at all, so he asks for your help.

For simplicity, Little Z provides a prime number $mod$, and you only need to output the expected value modulo $mod$.

Additionally, Little Z provides $n$ positive integers $d_1, d_2, \dots, d_n$. These positive integers satisfy the following constraints:

1. For any $d_i$, $d_i^{l_i} \equiv 1 \pmod{mod}$, and for all positive integers $t < l_i$, $d_i^t \not\equiv 1 \pmod{mod}$.
2. For any sequence of integers $(x_1, \dots, x_n)$ satisfying $\forall 1 \leq i \leq n, 0 \leq x_i \leq l_i - 1$, the condition $\sum_{i=1}^n p_i d_i^{x_i} \equiv 1 \pmod{mod}$ holds if and only if all $x_i = 0$.

Finally, Little Z guarantees that all $v_i$ are generated randomly, and the answer is meaningful modulo $mod$. Given the conditions described, the probability that a value cannot be represented modulo $mod$ during calculations is sufficiently small that it can be ignored.

Input

The first line contains three positive integers $n, mod, id$. Here, $id$ indicates that this test case satisfies the constraints of subtask $id$. In the test data, all test cases in the $i$-th subtask satisfy $id = i$.

The next $n$ lines each contain three positive integers $l_i, v_i, d_i$, with meanings as described in the problem.

Output

Output a single integer representing the expected value modulo $mod$.

Examples

Examples 1

2 1000000007 2
2 1 1000000006
2 1 1000000006

Output 1

833333342

Note 1

The properties of $x_1$ and $x_2$ are identical. Therefore, the states $(1, 0)$ and $(0, 1)$ after the first operation can be considered equivalent. We only consider the state $(1, 0)$.

If the next step increments the first integer again, the state becomes $(0, 0)$ and the game ends. The probability of this occurring is $\frac{1}{2}$, and the number of distinct sequences on the paper is $2$.

If the next step increments the second integer, the state becomes $(1, 1)$. The recorded states are $(1, 1), (1, 0)$. Consider the next time the first number is incremented:

If after reaching state $(1, 1)$ an even number of increments are applied to the second integer, then after this increment to the first integer, the state becomes $(0, 1)$. In this case, all four possible sequences appear on the paper when the game ends. The number of distinct sequences is $4$, and the probability is $\frac{1}{2} \times (\frac{1}{2} + \frac{1}{8} + \frac{1}{32} + \dots) = \frac{1}{3}$.

If after an odd number of increments the first number is incremented, the state becomes $(0, 0)$ and the game ends. In this case, the number of distinct sequences is $3$, and the probability is $\frac{1}{2} \times (\frac{1}{4} + \frac{1}{16} + \dots) = \frac{1}{6}$.

Therefore, the answer is $2 \times \frac{1}{2} + 3 \times \frac{1}{6} + 4 \times \frac{1}{3} = \frac{17}{6}$. Since $6 \times 166666668 \equiv 1 \pmod{10^9+7}$, the output value is $17 \times 166666668 \bmod (10^9+7) = 833333342$.

Examples 2~7

See the provided files.

Constraints

Let $m = \prod_{i=1}^n l_i$.

For all data, it is guaranteed that $1 \leq n, m \leq 5 \times 10^5$, $2 \leq l_i$, $1 \leq v_i \leq 10^6$, $1 \leq d_i \leq mod - 1$, and $9 \times 10^8 \leq mod \leq 1.05 \times 10^9$. The data satisfies all properties given in the problem description.

This problem uses bundled testing, and some subtasks have dependencies. You must pass all test cases in a subtask and all subtasks it depends on to pass that subtask.