Problem Background

Hakurei Reimu has a very large Yin-Yang Jade, which is one of her primary weapons.

However, the energy source of the Yin-Yang Jade comes from the accumulation of the owner's spiritual power. Therefore, Reimu always needs to maintain it in her daily life. Simply put, Reimu uses her spiritual power to obtain the energy required by the Yin-Yang Jade.

Problem Description

Spiritual power is divided into Yin and Yang. Initially, Reimu has only two Yang spiritual powers, which form a circle. Each time, Reimu can perform one of the following two operations:

• Insert a Yang spiritual power between two spiritual powers.
• Remove a Yang spiritual power.

To maintain stability, there should always be no less than two spiritual powers in the circle at any time.

Due to the instability of Yin and Yang, once a spiritual power experiences a change in its surroundings (an additional spiritual power or a reduction in spiritual power), it will change from Yang to Yin, or from Yin to Yang. However, if only the nature of the surrounding spiritual powers changes, it will not change.

Reimu will continuously adjust the spiritual powers until it finally reaches \( n \) (it may be more than \( n \) during the process). Then, Reimu will sequentially remove each spiritual power from a certain point in a clockwise or counterclockwise direction. It will form a chain. Reimu will use the energy in the chain to strengthen her Yin-Yang Jade.

This is very easy to achieve. But Reimu is very curious about how many different chains can be formed.

Due to Reimu's preferences, she may have \( m \) constraints. The \( i \)-th constraint \((p_i, c_i)\) specifies that the \( p_i \)-th spiritual power in the chain should be of a certain type. If \( c_i = 0 \), it should be Yin; otherwise, it should be Yang.

Since the possible results are too large, Reimu only needs the result modulo \( 998244353 \).

Two chains are considered different if and only if there is a position with a different color.

Input Format

The first line contains a positive integer \( n \) and a non-negative integer \( m \).

When \( m = 0 \), there are no constraint conditions. Otherwise, the next \( m \) lines each contain two non-negative integers \( p_i, c_i \), with meanings as described above.

Output Format

One line, a non-negative integer, representing the total number of possible chain types modulo \( 998244353 \).

Sample Input and Output

Sample Input #1

4 0

Sample Output #1

5

Sample Input #2

4 1
1 1

Sample Output #2

3

Sample Input #3

20 10
5 1
12 0
17 0
3 1
7 1
13 0
8 1
18 1
2 1
19 0

Sample Output #3

344

Notes

Sample Explanation

For Sample 1, the following two constructions are possible:

Where ADD denotes adding a Yang spiritual power and RMV denotes removing a Yang spiritual power.

The two rings obtained can be split into the following five chains:

• Ring 1: Yang—Yang—Yang—Yang.
• Ring 2: Yang—Yang—Yin—Yin, Yang—Yin—Yin—Yang, Yin—Yin—Yang—Yang, Yin—Yang—Yang—Yin.

Thus, the answer is \( 5 \).

For Sample 2, we have specified that the first spiritual power in the chain is Yang. Therefore, the result is \( 3 \).

Data Range

$$\def{\t}{\text}\def\arraystretch{1.5} \begin{array}{|c|c|c|c|}\hline \textbf{Subtask} & n\t{ 的范围} & m\t{ 的范围} & \t{分值}\cr\hline 1 & n\le 16 & m\le 16 & 15 \cr \hline 2 & n\le 10^6 & m\le 5\times 10^3 & 40 \cr \hline 3 & n\le 10^{18} & m=0 & 15 \cr \hline 4 & n\le 10^{18} & m\le 5\times 10^3 & 30 \cr \hline \end{array}$$

Additionally, for all data, \( 1 \le p_i \le n \), \( c_i \in \{0, 1\} \), \( 0 \le m \le n \), and \( p_i \) are distinct.

见题面 Input 部分

见题面 Output 部分