Expected Magic Energy

Meina is constructing a magic that is built in m+1 stages. In each of the first m stages (indexed by i from 1 to m), the success probability of each attempt is \(\frac{a_i}{b_i}\). In each stage, if an attempt fails, Meina only needs to retry the same stage; if it succeeds, she moves on to the next stage.

In the final, \( (m+1)\)-th stage, a magic base c is chosen. Namely, a positive integer \(r\) is generated uniformly at random in the range \(1 \le r \le 2n\) and \[ c=\cos \frac{r\pi}{n}, \] all in \(\LaTeX\) format. Finally, if she has performed a total of \(k\) attempts in the first m stages (each attempt – whether successful or not – counts), then the energy produced by the magic is \(c^k\).

Your task is to compute the expected energy produced by the magic. More precisely, let \(X_i\) be the (geometric) number of attempts in stage i so that the contribution of that stage is \[ E\Bigl[c^{X_i}\Bigr]=\frac{\frac{a_i}{b_i}c}{1-(1-\frac{a_i}{b_i})c}, \] and hence the overall energy is given by
\[ E[c^k]=\frac{1}{2n}\sum_{r=1}^{2n} \prod_{i=1}^{m}\frac{\frac{a_i}{b_i} c}{1-(1-\frac{a_i}{b_i}) c}\quad \text{with } c=\cos\frac{r\pi}{n}. \]

It can be shown that the final answer is a rational number. You only need to output the answer modulo 998244353.

inputFormat

The first line contains two integers \(m\) and \(n\).

Each of the following \(m\) lines contains two integers \(a_i\) and \(b_i\) representing the success probability \(\frac{a_i}{b_i}\) in stage \(i\).

Note: In the given problem, \(n\> is chosen so that all values \(\cos\frac{r\pi}{n}\) (for \(1\le r\le 2n\)) are rational numbers. For example, you may assume \(n=1,2,3\).

outputFormat

Output a single integer, the expected energy of the magic modulo 998244353.

sample

1 1
1 2

332748118