你有一个初始值为 $0$ 的数字 $x$ 以及一个素数 $p$。接下来，对于 $i = 1, 2, \dots, m$，你以概率 $q_i$ 将 $x$ 增加 $a_i$。求在过程结束时 $x$ 能被 $p$ 整除的概率。

该概率可以表示为一个有理数。请输出其对 $998\,244\,353$ 取模的结果。

输入格式

第一行包含两个整数 $p$ 和 $m$ ($2 < p < 30\,000$; $1 \le m \le 10^6$; $p$ 为素数)。

接下来的 $m$ 行，每行包含两个整数 $a_i$ 和 $r_i$ ($0 \le a_i < p$; $0 \le r_i \le 10^8$)。实际概率 $q_i$ 等于 $r_i/10^8$。

输出格式

输出一个整数，即答案对 $998\,244\,353$ 取模的结果。

形式化地，如果答案是一个有理数 $x/y$，请输出整数 $x \cdot y^{-1} \pmod{998\,244\,353}$。其中 $y^{-1}$ 是满足 $y \cdot y^{-1} \pmod{998\,244\,353} = 1$ 的整数。

样例

输入 1

2 3
0 100000000
1 100000000
1 50000000

输出 1

499122177