C. mathematican 的二进制

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

有一个长度很大的二进制串,初始时它的每一位都为 0。现在有 mm 个操作,其中第 ii 个操作是将这个二进制串的数值加上 2ai{2}^{a_i} (0ain)({0}\leq{a_i}\leq{n}),或者说,给第 aia_i 位加上 11 并进位,我们称每次操作的代价是这次操作改变的位的数量。例如,当前的二进制串是 1011110111 时,如果给它加上 202^0,串就变成了 1100011000,其中从低到高第 0,1,2,30,1,2,3 位发生了改变,那么这次操作代价为 44

我们以一定概率执行这些操作:第 ii 个操作有 pip_i 的概率执行,否则不执行。请求出所有执行的操作的代价和的期望。

你只需要求出期望改变的位数在模 998244353998244353 意义下的值。具体来说,如果你算出来的期望E=PQE = {\frac{P}{Q}},其中 P,QP,Q 互质,那么你只要输出 (PQ1)(mod998244353)({P}{Q^{-1}})\pmod{998244353},其中 Q1(mod998244353)Q^{-1}\pmod{998244353} 表示 QQ(mod998244353)\pmod{998244353} 意义下的逆元。

注意:执行完操作后,该串去除前导 00 后的长度可能大于 nn

输入格式

第一行两个用空格分隔的正整数 n,mn,m,分别表示 aia_i 的范围和操作数,如上文所述。

接下来 mm 行,每行三个正整数 ai,xi,yia_i, x_i, y_i,其中 pi=xiyip_i = {\frac{x_i}{y_i}}

输出格式

仅一行,表示答案。

样例

样例输入 1

4 4
0 1 2
0 1 2
0 1 2
0 1 2

样例输出 1

187170819

样例输入 2

233 6
1 166 233
2 233 666
3 166 266
4 233 266
5 233 666
6 166 233

样例输出 2

56615945

样例 3

见附加文件。

数据范围与提示

对于所有数据,1n,m200000,0x<998244353,1y<9982443531\le {n,m} \leq{200000}, 0\le x<998244353,1\le y<998244353

子任务编号 分值 nn \leq mm\leq 特殊限制
1 55 1717 1717 -
2 1515 11 30003000 ai=0a_i=0
3 2020 11 2×1052\times 10^5 ai=0a_i=0
4 2020 30003000 30003000 -
5 4040 10510^5 2×1052\times 10^5 -