#P18301. Random Sum

Random Sum

Random Sum

给定一个素数 pp,以及一个初始值为 00 的整数 xx。

依次进行 mm 次操作。第 ii 次操作中,以概率 qiq_i 将 xx 增加 aia_i,以概率 1−qi1-q_i 保持 xx 不变。各次操作相互独立。

求全部操作结束后,xx 能被 pp 整除的概率。将答案对 998244353998244353 取模后输出。

输入格式

第一行包含两个整数 p,mp,m,其中 pp 是素数。

接下来 mm 行,每行包含两个整数 ai,ria_i,r_i,表示第 ii 次操作,其中

qi=ri108.q_i=\frac{r_i}{10^8}.

所有输入满足:

  • 2≤p<300002\le p<30000,且 pp 为素数;
  • 1≤m≤1061\le m\le 10^6;
  • 0≤ai<p0\le a_i<p;
  • 0≤ri≤1080\le r_i\le 10^8。

本题只有一组输入,没有测试组数 TT。

输出格式

输出一个整数,表示所求概率对 998244353998244353 取模的结果。

具体地,若该概率表示为有理数 u/vu/v,则输出

u⋅v−1 mod 998244353,u\cdot v^{-1}\bmod 998244353,

其中 v−1v^{-1} 是 vv 在模 998244353998244353 意义下的乘法逆元。由于所有概率的分母都是 10810^8 的幂,所需逆元一定存在。

样例

2 3
0 100000000
1 100000000
1 50000000
499122177

样例说明

第一次操作不改变 xx;第二次操作必定使 x=1x=1。最后一次操作以 1/21/2 的概率使 x=2x=2,因此所求概率为 1/21/2,其模意义下的值为 499122177499122177。