Maya: If you dare to summon your courage and try to seize my golden cup, Show me the tide of supreme wrath. Do not waver with the hidden undercurrents in your heart, Nor fade with the waxing and waning of the moon. From your pupils, scatter the radiance of feldspar, From within your chest, chant the beauty of a desperate, arrogant gamble. Declare war and never retreat.

Maya: The earth's chest heaves beneath the thin veil, That is the kingdom lit by the morning glow. Spread your wings until the air is thin, Chase the scorching sun until it burns me. So it is said, do not be silent. The cold wind strikes the midnight bell, Thus Spoke Zarathustra, eternal. This is the outline of my pride.

— Pride and Arrogance (Chinese lyrics: Shui Xi, Miss Veder)

The theme of the day is "Pride Revue".

Karen is fighting against Maya. They are standing on a number line. In each round, Karen might take the upper hand and move forward by one unit, but more often she is knocked back. Specifically, there are $k$ possible ways she can be knocked back by $a_i$ units, each with a weight of $b_i$.

During the battle, any floor tiles they touch are destroyed. Note that if Karen is knocked back from position $x$ to position $y$, the tiles between $y+1$ and $x-1$ are not destroyed. The tiles they start on are also destroyed.

I (the Giraffe) am curious about the total number of floor tiles destroyed during the battle (of course, a tile at a specific position is only counted as one destroyed tile even if it is destroyed multiple times). Please help me calculate the sum of the number of destroyed tiles over all possible scenarios occurring over $n$ rounds. You only need to provide the answer modulo $998244353$.

Wakarimasu!

Input

The first line contains two positive integers $n$ and $k$.

The next $k$ lines each contain two positive integers $a_i$ and $b_i$.

Output

Output the answer.

Examples

Input 1

1 1
1 2

Output 1

6

Note

Whether moving forward by 1 unit or being knocked back by 1 unit, a total of 2 tiles are destroyed. There are 3 such scenarios in total. Thus, $2 \times 3 = 6$.

Input 2

20 5
1 2
3 1
5 1
9 2
10 1

Output 2

728464158

Data Range

For 100% of the data, it is guaranteed that $1 \le n \le 3 \times 10^6$, $1 \le k \le 20$, $1 \le a_i \le n$, $1 \le b_i < 998244353$, and all $a_i$ are distinct.

• Test cases $1 \le i \le 10$: $n = 2^i$.
• Test cases $11 \le i \le 14$: $n \le 5 \times 10^4, k \le 5$.
• Test cases $15 \le i \le 17$: $a_i \le 5$.
• Test cases $18 \le i \le 20$: No special restrictions.