超越（Transcendent）

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