{"raw_statement":[{"iden":"background","content":"越过领域和现实的终极存在 —— 超越。\n\n****\n「超越之光」美娜，是亚特兰蒂斯最强的魔法师，亦是无人能及的贤者。即便如此，她也一刻都没有停下对数学的探索。\n\n「最高次系数为 $1$ 的整系数多项式方程的解不一定是整数，」美娜自言自语道，「但是其所有根组成的对称多项式的值必然是整数。」\n\n「这很容易证明，却也很有趣呢。」想到这里，美娜突然有了开发新魔法的思路。"},{"iden":"statement","content":"美娜的魔法需要 $m+1$ 个阶段来构建。第 $i \\ (1 \\leq i \\leq m)$ 个阶段每次尝试的成功概率为 $a_i/b_i$，如果失败**只需要重试当前阶段**即可，如果成功就能进入下一个阶段。\n\n最后的第 $m+1$ 个阶段需要选一个魔力基数 $c$。不过这个魔法现在并不稳定，设 $r$ 是一个不大于 $2n$ 的范围内**均匀随机**生成的正整数，则\n$$c=\\cos \\frac{r\\pi}{n}$$\n最后，若美娜在前 $m$ 个阶段中总共尝试了 $k$ 次（每次无论失败或成功，都算多一次尝试），她的魔法会产生 $c^k$ 的能量。\n\n美娜想知道这个魔法所产生能量的期望值是多少，当然她很容易就算出了答案，你能帮她验算一下吗？\n\n你只用输出答案对 $998244353$ 取模的结果即可。显然，答案一定是有理数，所以你可以简单地计算其对 $998244353$ 取模的值。"},{"iden":"input","content":"第一行两个正整数 $n,m$。  \n接下来 $m$ 行，每行两个正整数 $a_i,b_i$，意义如题目描述。"},{"iden":"output","content":"输出一行一个整数，表示答案。"},{"iden":"note","content":"【样例 $1$ 解释】\n\n此时 $m=3$，前 $m$ 个阶段中，第一阶段的成功概率为 $1/2$，之后两个阶段的成功概率都为 $2/3$。由此可以算出，恰好尝试 $k \\ (k \\geq m)$ 次完成前 $m$ 个阶段的概率为（我有一个巧妙的方法给出证明，可惜这里空间太小，写不下）：\n\n$$p_k=2^{4-k}-4(k+1)3^{1-k}$$\n例如 $p_3=2/9$，这是每个阶段都一次成功的概率 $1/2 \\times 2/3 \\times 2/3$。  \n又如 $p_4=7/27$，这要求在某一阶段尝试恰好两次，其它阶段都一次成功，即：\n$$p_4=\\left( \\frac 12\\right)^2   \\frac 23 \\cdot \\frac 23+\\frac 12\\left( \\frac 29\\right)\\frac 23+\\frac 12\\cdot \\frac 23\\left( \\frac 29\\right)$$\n样例中 $n=2$，可知 $c=1$ 的概率为 $1/4$，$c=-1$ 的概率为 $1/4$，还有 $1/2$ 的概率 $c=0$。故答案为\n\n$$\\frac 14\\sum_{k\\geq 3}p_k (1+(-1)^k)=\\frac{11}{48}$$\n对 $998244353$ 取模后为 $103983787$。\n\n【样例 $2$ 解释】\n\n取模前的答案为 $\\dfrac{24284321}{191028915}$。\n\n【数据范围】 \n\n**本题使用捆绑测试。**\n\n\nSubtask 1（7 pts）：$n\\le 6$，$m=1$；   \nSubtask 2（9 pts）：$n\\le 6$，$m\\le 10$；  \nSubtask 3（13 pts）：$n\\le 500$，$m\\le 500$；   \nSubtask 4（13 pts）：$n=2^{19}$；  \nSubtask 5（15 pts）：$n \\le 10^5$，$m\\le 500$；  \nSubtask 6（15 pts）：不同的 $a_i/b_i$ 最多有两组；   \nSubtask 7（28 pts）：无特殊限制。\n\n\n对于全部数据，$1\\le n \\le 10^8$，$1\\le m \\le 60000$，$1\\le a_i<b_i\\leq 10^8$。且保证\n\n$$U_n\\left( \\frac{b_i}{b_i-a_i}\\right)\\not \\equiv 0 \\pmod{998244353}$$\n其中 $U_n(x)$ 表示 $n$ 次的[第二类 Chebyshev 多项式](https://mathworld.wolfram.com/ChebyshevPolynomialoftheSecondKind.html)。\n\n【提示】   \n你在找什么呢？或许可以再看看题目背景，会有帮助的。"}],"translated_statement":null,"sample_group":[["2 3\n1 2\n2 3\n2 3","103983787"],["4 5\n1 3\n1 2\n1 4\n1 5\n1 6","525030616"],["7 17\n1 5\n1 5\n1 5\n1 5\n1 3\n1 3\n1 3\n1 2\n1 2\n1 6\n1 6\n1 6\n1 6\n1 6\n1 6\n1 6\n1 6","308796722"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}