Background

Transcending realms and reality — the ultimate existence.

Minna, the "Transcendent Light," is the strongest magician of Atlantis and an unmatched sage. Despite this, she never ceases her exploration of mathematics.

"The solutions of a polynomial equation with integer coefficients and leading coefficient 1 are not necessarily integers," Minna mused, "but the value of the symmetric polynomial formed by all its roots is certainly an integer."

"It's easy to prove and quite interesting." This thought suddenly gave Minna an idea for developing a new spell.

Problem Description

Minna's spell requires $m+1$ stages to construct. In the $i$-th stage $(1 \leq i \leq m)$, the success probability for each attempt is $a_i/b_i$. If the attempt fails, she only needs to retry the current stage; if it succeeds, she can move to the next stage.

The final $(m+1)$-th stage requires selecting a magic base $c$. However, this spell is currently unstable. Let $r$ be a positive integer uniformly randomly generated within the range of $1$ to $2n$, then
$$c=\cos \frac{r\pi}{n}$$
Finally, if Minna has attempted $k$ times in total (each attempt, whether successful or not, counts as one attempt) in the first $m$ stages, her spell will generate $c^k$ energy.

Minna wants to know the expected value of the energy generated by this spell. She has already calculated the answer easily, but can you help her verify it?

You only need to output the result modulo $998244353$. Clearly, the answer is a rational number, so you can simply calculate its value modulo $998244353$.

Input Format

The first line contains two positive integers $n, m$.
The next $m$ lines each contain two positive integers $a_i, b_i$, as described in the problem statement.

Output Format

Output a single integer, representing the answer.

Sample Input and Output

Sample Input #1

2 3
1 2
2 3
2 3

Sample Output #1

103983787

Sample Input #2

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

Sample Output #2

525030616

Sample Input #3

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

Sample Output #3

308796722

Notes

Sample 1 Explanation

Here, $m=3$, and in the first $m$ stages, the success probability for the first stage is $1/2$, and for the next two stages, it is $2/3$. From this, we can calculate the probability of exactly $k$ attempts $(k \geq m)$ to complete the first $m$ stages as:

$$p_k=2^{4-k}-4(k+1)3^{1-k}$$
For example, $p_3=2/9$, which is the probability of succeeding in each stage on the first try: $1/2 \times 2/3 \times 2/3$.
Another example, $p_4=7/27$, which requires exactly two attempts in one stage, with the other stages succeeding on the first try:
$$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)$$
In this sample, $n=2$, so the probability of $c=1$ is $1/4$, the probability of $c=-1$ is $1/4$, and the probability of $c=0$ is $1/2$. Therefore, the answer is

$$\frac 14\sum_{k\geq 3}p_k (1+(-1)^k)=\frac{11}{48}$$
which modulo $998244353$ is $103983787$.

Sample 2 Explanation

The answer before modulo is $\dfrac{24284321}{191028915}$.

Data Range

This problem uses batched testing.

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): At most two different values of $a_i/b_i$;
Subtask 7 (28 pts): No additional constraints.

For all data, $1\le n \le 10^8$, $1\le m \le 60000$, $1\le a_i<b_i\leq 10^8$. It is guaranteed that

$$U_n\left( \frac{b_i}{b_i-a_i}\right)\not \equiv 0 \pmod{998244353}$$
where $U_n(x)$ denotes the $n$-th Chebyshev polynomial of the second kind.

Hints

What are you looking for? Perhaps you could revisit the problem background for some insights.

见题面 Input 部分

见题面 Output 部分