Random Sum
给定一个素数 p,以及一个初始值为 0 的整数 x。
依次进行 m 次操作。第 i 次操作中,以概率 qi 将 x 增加 ai,以概率 1−qi 保持 x 不变。各次操作相互独立。
求全部操作结束后,x 能被 p 整除的概率。将答案对 998244353 取模后输出。
输入格式
第一行包含两个整数 p,m,其中 p 是素数。
接下来 m 行,每行包含两个整数 ai,ri,表示第 i 次操作,其中
qi=108ri.
所有输入满足:
- 2≤p<30000,且 p 为素数;
- 1≤m≤106;
- 0≤ai<p;
- 0≤ri≤108。
本题只有一组输入,没有测试组数 T。
输出格式
输出一个整数,表示所求概率对 998244353 取模的结果。
具体地,若该概率表示为有理数 u/v,则输出
u⋅v−1mod998244353,
其中 v−1 是 v 在模 998244353 意义下的乘法逆元。由于所有概率的分母都是 108 的幂,所需逆元一定存在。
样例
2 3
0 100000000
1 100000000
1 50000000
499122177
样例说明
第一次操作不改变 x;第二次操作必定使 x=1。最后一次操作以 1/2 的概率使 x=2,因此所求概率为 1/2,其模意义下的值为 499122177。