题目背景

小 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}^nv_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 完全不会这个问题，因此小 Z 请求您帮助他解决这个问题。

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

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

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

最后，小 Z 保证所有 $v_i$ 随机生成，且答案在模 $mod$ 下有意义。在满足题目所述条件的情况下，运算中出现值在模 $mod$ 意义下无法表示的概率足够小，可以认为不用考虑出现值在模 $mod$ 意义下无法表示的情况。

输入格式

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

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

输出格式

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

样例

样例输入 #1

2 1000000007 2
2 1 1000000006
2 1 1000000006

样例输出 #1

833333342

样例解释

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

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

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

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

如果经过了奇数次后下一次给第一个数加一，则状态变为 $(0,0)$，游戏结束。此时不同的序列数为 $3$，概率为 $\frac 12*(\frac 14+\frac 1{16}+...)=\frac 16$

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

样例 #2~#7

见下发文件

数据范围与限制

记 $m=\prod_{i=1}^nl_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$。数据满足题目描述中给出的所有性质。

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

时间限制：4s

空间限制：1024MB