良心题(number)

题目描述

某一天，zzh 和 cjz 在进行一个神仙的游戏。

zzh 选定了一个正整数 $n$ ，以及 $n$ 个不小于 $2$ 的正整数 $v_1,...,v_n$。

cjz 随后选定了 $n$ 个正整数 $p_1,...,p_n$，以及一个正整数 $k$ 。

然后游戏开始，这个游戏中只包含 $n$ 个数 $x_1,...,x_n$ ，以及一个计数器 $ct$ 。初始时这些数都等于 $0$ 。

在这个游戏中只存在一种操作，操作的描述如下：

首先，通过 $p$ 随机生成一个 $[1,n]$ 间的正整数 $t$。生成 $1$ 的概率为 $\frac{p_1}{\sum_{i=1}^np_i}$ ， 生成 $2$ 的概率为 $\frac{p_2}{\sum_{i=1}^np_i}$ ，...，生成 $x$ 的概率为 $\frac{p_x}{\sum_{i=1}^np_i}$ 。

然后，将 $x_t$ 变为 $(x_t+1)\bmod v_t$。

最后，如果此时所有 $x_i$ 均为 $0$ ，则将计数器 $ct$ 加一。当 $ct=k$ 时，游戏停止。

游戏的过程即为循环执行这个操作，直到游戏停止。

现在 zzh 和 cjz 都选好了所有的数，在游戏开始前，他们各自提出了一个问题：

zzh 想知道，在游戏停止时，进行的操作的次数的期望。(结束时的这次操作计入操作次数)。

cjz 想知道，如果定义一次游戏的丰富程度为：

定义一个长度为 $n$ 的整数序列 $s_1,...,s_n$ 是好的，当且仅当：

在游戏的某次操作后， $\forall i\in\{1,2,...,n\},x_i=s_i$ ，即序列 $s$ 与序列 $x$ 相等。

游戏的丰富程度为好的整数序列 $s_1,...,s_n$ 的数量。

则游戏的丰富程度的期望。

zzh 和 cjz 很快求出了两个问题的答案。现在他们把问题交给了你。为了让不是神仙的人(比如你)能够回答问题，cjz 选定了一个质数 $p$ ，满足：

1. $\forall i\in\{1,2,...,n\},v_i|p-1$
2. 保证答案在模 $p$ 意义下有定义。
3. $3$ 是模 $p$ 意义下的一个原根。
4. 对于游戏中任何一个可能出现的 $x_{1,...,n}$，从这个状态开始操作，到计数器下一次增加的操作次数的期望值模 $p$ 意义下有定义.
5. 所有的 $p_i$ 随机生成，$p$ 在某个范围内满足条件的数中随机生成。可以认为，在这个条件以及上个条件的限制下，有极其大的概率不用考虑计算中出现分母模意义下为 $0$ 的情况。

你只需要求出答案对 $p$ 取模的结果即可。

输入格式

从文件 number.in 读入。

输入的第一行包含四个正整数 $n,p,k,op$ ，其中 $op$ 表示你需要回答的问题。如果 $op=1$ ，你需要回答 zzh 的问题。如果 $op=2$ ，你需要回答 cjz 的问题。

接下来的 $n$ 行，第 $i$ 行包含两个正整数 $v_i,p_i$ ，含义见题面。

输出格式

输出到文件 number.out。

输出一行一个整数，表示答案对 $p$ 取模的结果。

样例

样例输入1

2 998244353 1 1
2 1
2 1

样例输出1

4

样例解释1

设 $f_{a_1,a_2}$ 表示当前两个数为 $a_1,a_2$ 时，游戏结束需要的操作次数期望。

那么：

$$f_{0,0}=1+\frac12f_{0,1}+\frac12f_{1,0}\\ f_{0,1}=1+\frac12f_{1,1}\\ f_{1,0}=1+\frac12f_{1,1}\\ f_{1,1}=1+\frac12f_{0,1}+\frac12f_{1,1} $$

可以解得 $f_{0,0}=f_{1,1}=4,f_{0,1}=f_{1,0}=3$

样例输入2

2 998244353 1 2
2 1
2 1

样例输出2

831870297

样例解释2

考虑计算某个状态不出现的概率。

状态 $1,1$ 不出现，当且仅当操作为连续两次选中同一个变量，这样的概率为 $\frac12$。

状态 $0,1$ 不出现，当且仅当第一次选第一个变量，随后选择偶数次第二个变量，再选择第一个变量使游戏结束。这样的概率为 $\frac12*\frac23=\frac13$

状态 $1,0$ 与状态 $0,1$ 的答案相同。

因此答案为 $1+\frac12+2*\frac23=\frac{17}6$

样例输入3

2 998244353 1 2
2 2
2 3

样例输出3

517661003

样例输入4

2 998244353 100 2
2 2
2 3

样例输出4

313130520

样例输入/输出 5~10

见下发文件

样例 $5\sim 10$ 依次满足测试点 $4,8,10,13,18,24$ 的限制。

数据范围与限制

对于所有数据，保证 $\prod_{i=1}^n v_i\leq 2^{19},1<v_i\leq 2^{19},1\leq p_i\leq 10^5,5\times 10^8\leq p\leq 1.05\times 10^9,op\in\{1,2\},k\leq 10^8$，$p$ 为质数。保证数据满足题面中所有限制。

测试点编号	特殊限制
$1$	$op=1,n=1$
$2,3$	$op=1,\prod_{i=1}^n v_i\leq 500$
$4,5$	$op=1,\prod_{i=1}^n v_i\leq 10^4$
$6$	$op=1$
$7$	$op=2,n=1$，满足性质A,B
$8,9$	$op=2,\prod_{i=1}^n v_i\leq 200$，满足性质A,B
$10,11,12$	$op=2,\prod_{i=1}^n v_i\leq 600$，满足性质A,B
$13,14,15,16$	$op=2,\prod_{i=1}^n v_i\leq 3000$，满足性质A,B
$17$	$op=2,\prod_{i=1}^n v_i\leq 10^4$，满足性质A,B
$18$	$op=2,\prod_{i=1}^n v_i\leq 2^{17}$，满足性质A,B
$19$	$op=2$，满足性质A,B
$20$	$op=2,\prod_{i=1}^n v_i\leq 2^{17}$，满足性质A
$21$	$op=2$，满足性质A
$22$	$op=2,\prod_{i=1}^n v_i\leq 2^{17}$，满足性质B
$23$	$op=2$，满足性质B
$24$	$op=2,\prod_{i=1}^n v_i\leq 2^{17}$
$25$	$op=2$

特殊性质A：$\forall i\in\{1,2,...,n\},\exists t\in\N,v_i=2^t$

特殊性质B: $2^{20}|p-1$

友情提示：读题不规范，爆零两行泪。