Background

The ultimate existence that goes beyond domains and reality—Transcendence.

---

“Light of Transcendence” Mina is Atlantis’s strongest mage and an unmatched sage. Even so, she never stopped exploring mathematics for a moment.

“The solutions of a monic integer-coefficient polynomial equation are not necessarily integers,” Mina murmured to herself, “but the value of any symmetric polynomial in all its roots must be an integer.”

“This is easy to prove, yet also quite interesting.” Thinking of this, Mina suddenly got an idea for developing new magic.

Problem Description

Mina’s magic needs $m+1$ stages to build. In stage $i \ (1 \leq i \leq m)$, each attempt succeeds with probability $a_i/b_i$. If it fails, you only need to retry the current stage; if it succeeds, you can enter the next stage.

The final stage $m+1$ requires choosing a magic base $c$. However, this magic is currently unstable. Let $r$ be a positive integer generated uniformly at random in the range not exceeding $2n$. Then

$$c=\cos \frac{r\pi}{n}$$

Finally, if Mina made a total of $k$ attempts in the first $m$ stages (each attempt counts, regardless of failure or success), her magic will produce energy $c^k$.

Mina wants to know the expected value of the energy produced by this magic. Of course, she has computed the answer easily. Can you help her verify it?

You only need to output the answer modulo $998244353$. Clearly, the answer must be a rational number, so you can directly compute 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$, with meanings as described in the statement.

Output Format

Output one line containing one integer, which is the answer.

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

Hint

[Explanation for Sample 1]

Here $m=3$. In the first $m$ stages, the success probability of the first stage is $1/2$, and the success probabilities of the next two stages are both $2/3$. From this, we can compute that the probability of finishing the first $m$ stages in exactly $k \ (k \geq m)$ attempts is (I have a clever way to prove it, but unfortunately there is too little space to write it down):

$$p_k=2^{4-k}-4(k+1)3^{1-k}$$

For example, $p_3=2/9$, which is the probability that every stage succeeds in one attempt: $1/2 \times 2/3 \times 2/3$.
Another example is $p_4=7/27$. This requires that in some stage there are exactly two attempts, while all other stages succeed in one attempt, i.e.:

$$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 the sample, $n=2$. Thus, the probability that $c=1$ is $1/4$, the probability that $c=-1$ is $1/4$, and with probability $1/2$ we have $c=0$. Therefore the answer is

$$\frac 14\sum_{k\geq 3}p_k (1+(-1)^k)=\frac{11}{48}$$

Taking modulo $998244353$, it equals $103983787$.

[Explanation for Sample 2]

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

[Constraints]

This problem uses bundled testdata.

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): There are at most two distinct groups of $a_i/b_i$.
Subtask 7 (28 pts): No special restrictions.

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 also 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.

[Hint]
What are you looking for? Maybe you can take another look at the background; it might help.

Translated by ChatGPT 5