题目背景

越过领域和现实的终极存在 —— 超越。

---

「超越之光」美娜，是亚特兰蒂斯最强的魔法师，亦是无人能及的贤者。即便如此，她也一刻都没有停下对数学的探索。

「最高次系数为 $1$ 的整系数多项式方程的解不一定是整数，」美娜自言自语道，「但是其所有根组成的对称多项式的值必然是整数。」

「这很容易证明，却也很有趣呢。」想到这里，美娜突然有了开发新魔法的思路。

题目描述

美娜的魔法需要 $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$ 取模的值。

输入格式

第一行两个正整数 $n,m$。
接下来 $m$ 行，每行两个正整数 $a_i,b_i$，意义如题目描述。

输出格式

输出一行一个整数，表示答案。

2 3
1 2
2 3
2 3

103983787

4 5
1 3
1 2
1 4
1 5
1 6

525030616

7 17
1 5
1 5
1 5
1 5
1 3
1 3
1 3
1 2
1 2
1 6
1 6
1 6
1 6
1 6
1 6
1 6
1 6

308796722

提示

【样例 $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 多项式。

【提示】
你在找什么呢？或许可以再看看题目背景，会有帮助的。