The world has been invaded by monsters! Little W wants to rebuild the world, and he must first eliminate all the monsters.

There are a total of $n$ monsters. The $i$-th monster has $a_i$ health and $b_i$ explosion damage. The health values of all monsters are distinct. A monster is considered dead when its health is less than or equal to 0; otherwise, it is alive. When the $i$-th monster dies, it deals $b_i$ explosion damage to all other living monsters.

Little W is the hero chosen by the world. He possesses a holy sword that can deal $+\infty$ damage to any single monster in one use. However, the holy sword cannot be used infinitely, so Little W wishes to minimize the number of times he uses it.

Unfortunately, the detection device has been interfered with, and Little W only knows that $b_i$ is an integer within a small interval $[l_i, r_i]$.

Now, Little W wants to know the sum of the minimum number of times he must use the holy sword across all possible sequences $\{b_i\}$. Little W has a special ability: he only needs to know the result of this sum modulo $M$.

Input

The first line contains three integers $n, m, M$, where $m$ is the upper bound of the interval for $b_i$.

The next $n$ lines each contain three integers $a_i, l_i, r_i$, representing the health of the $i$-th monster and the interval $[l_i, r_i]$ for $b_i$, with the guarantee that $r_i \le m$.

Output

Output a single integer representing the answer.

Examples

Input 1

4 2 308641732
8 1 1
5 1 2
2 1 1
3 1 2

Output 1

8

Note 1

There are a total of four possible sequences $\{b_i\}$. Taking $\{1, 1, 1, 1\}$ as an example:

The health and explosion damage of the monsters can be represented as the tuples $\{(8, 1), (5, 1), (2, 1), (3, 1)\}$. The optimal strategy is to use the holy sword on $(8, 1)$ and $(5, 1)$. At this point, 2 explosion damage is dealt, causing $(2, 1)$ to die, which then deals 1 explosion damage, resulting in a total of 3 explosion damage, which in turn causes $(3, 1)$ to die. The number of uses is 2.

Similarly, for all cases, the number of times the holy sword is used is 2, so the answer is $2 \times 4 = 8$.

Constraints

For all test data, it is guaranteed that: $1 \le n \le 20$, $1 \le l_i \le r_i \le m \le 15$, $1 \le a_i \le 300$, $2 \le M \le 10^9 + 7$.

Note

Trust the constants.