题目背景

小 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$ 取模的结果。

2 1000000007 2
2 1 1000000006
2 1 1000000006

833333342

数据范围与提示

记 $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$。数据满足题目描述中给出的所有性质。

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

子任务编号	子任务分值	特殊限制	子任务依赖
$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之内切掉这道题。