题目背景

小 Z 是一个非常菜的 OIer。

小 Z 完全不会出题，距离交题的期限还剩一天时，他还是没有任何想法。

因此，他选了一道非常简单的题，他希望参加比赛的所有人都能在这道题上获得 100 分的好成绩。

题目描述

小 Z 喜欢数字。小 Z 想到了这样一个游戏：

小 Z 有 $n$ 个数字 $x_1,...,x_n$。在游戏开始前（即时刻 0），这些数字的值都是 $0$。

小 Z 有一个生成 $[1,n]$ 间整数的随机数生成器。这个随机数生成器有 $n$ 个正整数参数 $v_1,...,v_n$。记 $p_i = \frac{v_i}{\sum_{j=1}^n v_j}$，它生成一个随机数时，生成 $1$ 的概率为 $p_1$，...，生成 $x$ 的概率为 $p_x$，...，生成 $n$ 的概率为 $p_n$。

小 Z 还有 $n$ 个大于 $1$ 的正整数 $l_1,...,l_n$，其中第 $i$ 个数 $l_i$ 的意义是所有对 $x_i$ 的操作在 $\bmod l_i$ 意义下进行。

在游戏中，小 Z 在每个时刻会依次进行如下操作：

1. 使用随机数生成器生成一个整数。设生成的整数为 $k$，小 Z 会将第 $k$ 个数字加一，并进行取模。即令 $x_k \leftarrow (x_k + 1) \bmod l_k$。
2. 将当前所有数字按顺序构成的序列 $(x_1,x_2,...,x_n)$ 记录在纸上。可以认为纸的长度是无限的。

当某个时刻小 Z 记录了全零的序列 $(0,0,...,0)$ 时，小 Z 会意识到所有数字都回到了最开始的状态，此时他会结束这次游戏。

小 Z 不关心游戏持续的时间，他更想知道纸上会出现多少种不同的序列 $(x_1,x_2,...,x_n)$。因此他希望求出在游戏结束时，纸上不同的序列 $(x_1,x_2,...,x_n)$ 的种类数的期望值。

为了简便，小 Z 给出了一个质数 $mod$，你只需要回答期望值对 $mod$ 取模的结果。

同时，小 Z 还给出了 $n$ 个正整数 $d_1,d_2,...,d_n$。这些正整数满足如下限制：

• 对于任意一个 $d_i$，满足 $d_i^{l_i} \equiv 1 \ (\bmod \ mod)$，且对于所有小于 $l_i$ 的正整数 $t$，$d_i^t \not\equiv 1 \ (\bmod \ mod)$。
• 对于任意一组满足 $\forall 1\leq i\leq n, 0\leq x_i\leq l_i-1$ 的整数序列 $(x_1,...,x_n)$，满足 $\sum_{i=1}^n p_i d_i^{x_i} \equiv 1 \ (\bmod \ mod)$ 当且仅当所有 $x_i = 0$。

最后，小 Z 保证所有 $v_i$ 随机生成，且答案在模 $mod$ 下有意义。

输入格式

输入第一行包含三个正整数 $n, mod, id$。其中 $id$ 表示这个测试点满足 $id$ 号子任务的限制。在测试数据中，第 $i$ 个子任务中的所有测试点满足 $id = i$。

接下来 $n$ 行，第 $i$ 行包含三个正整数 $l_i, v_i, d_i$，含义见题目描述。

输出格式

输出一行一个整数，表示期望值对 $mod$ 取模的结果。

样例

输入

2 1000000007 2
2 1 1000000006
2 1 1000000006

输出

833333342

$x_1, x_2$ 的性质完全相同。因此第一次操作后 $(1,0)$ 和 $(0,1)$ 两种状态可以看做等价。只考虑为 $(1,0)$ 的状态。

如果下一步仍然给第一个整数加一，则状态变为 $(0,0)$，游戏结束。这种情况出现的概率为 $\frac{1}{2}$，纸上不同的序列数为 $2$。

如果下一步给第二个整数加一，此时状态变为 $(1,1)$。此时记录的状态为 $(1,1),(1,0)$，考虑下一次给第一个数加一时：

• 如果在到达状态 $(1,1)$ 后又经过了偶数次给第二个数加一，则这次给第一个数加一后状态为 $(0,1)$。因此这种情况中游戏结束时四种可能的序列都会出现在纸上。不同的序列数为 $4$，概率为 $\frac{1}{2} \times (\frac{1}{2} + \frac{1}{8} + \frac{1}{32} + \ldots) = \frac{1}{3}$
• 如果经过了奇数次后下一次给第一个数加一，则状态变为 $(0,0)$，游戏结束。此时不同的序列数为 $3$，概率为 $\frac{1}{2} \times (\frac{1}{4} + \frac{1}{16} + \ldots) = \frac{1}{6}$

因此答案为 $2 \times \frac{1}{2} + 3 \times \frac{1}{6} + 4 \times \frac{1}{3} = \frac{17}{6}$。因为 $6 \times 166666668 \equiv 1 \ (\bmod \ 10^9 + 7)$，因此输出的值为 $17 \times 166666668 \bmod (10^9 + 7) = 833333342$。

数据范围与提示

记 $m = \prod_{i=1}^n l_i$。

对于所有数据，保证 $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$，$9 \times 10^8 \leq mod \leq 1.05 \times 10^9$。数据满足题目描述中给出的所有性质。

本题使用捆绑测试，对于部分子任务有子任务依赖。你需要通过一个子任务中的所有测试点以及这个子任务依赖的所有子任务才能通过这个子任务。

子任务编号	子任务分值	特殊限制	子任务依赖
1	2	$n = 1$
2	8	$m \leq 8$
3	10	$m \leq 100$	2
4	8	$n = 2, mod = 998244353, m \leq 2^{10}$
5	10	$l_i = 2, m \leq 2^{10}$
6	12	$m \leq 2^{10}$	3,4,5
7	8	$m \leq 2^{13}$	6
8	6	$n = 2, mod = 998244353$	4
9	8	$mod = 998244353$	8
10	$10$	$l_i = 2$	5
11	12	$l_i \leq 50$	10
12	6	无特殊限制	7,9,11

小Z在这里立了一个flag：id以D,M和T开头的选手可以在30min之内切掉这道题。