Spiritual Chain Formation

Reimu starts with two yang spiritual powers arranged in a circle (i.e. initially the circle is [1, 1] where 1 means yang and 0 means yin). She may adjust the circle by performing one of the following two operations any number of times (the circle always has at least two elements):

• Insertion: Select two adjacent spiritual powers and insert a new yang (value 1) between them. At the moment of insertion the two neighboring powers are forced to flip their nature (i.e. if a neighbor was yang it becomes yin and vice‐versa). In other words, if the two adjacent elements have values \(a\) and \(b\) (each 0 or 1) then after the insertion they become \(1-a\) and \(1-b\), and the newly inserted element is 1. The final change in the number of yang is \[ \Delta = 3 - 2(a+b), \] which is always odd.
• Removal: Remove a yang spiritual power. Its two adjacent neighbors (which become adjacent after removal) will each flip their value. If the two neighbors had values \(a\) and \(b\) before the operation then after removal they become \(1-a\) and \(1-b\). The change in the number of yang is \[ \Delta = 1 - 2(a+b). \]

Reimu will perform operations until the circle contains exactly n spiritual powers. (Note that along the way the circle may temporarily have more than n elements.) After that, starting from some point she removes the powers one by one in either clockwise or anticlockwise order to form a chain (a linear sequence of length n). Two chains are considered different if they differ in at least one position.

Because Reimu is curious, she wonders how many different chains may be formed. Moreover, she might have m restrictions. The i-th restriction is a pair \((p_i,c_i)\) meaning that the pi-th element of the chain must be of type yin (if \(c_i=0\)) or yang (if \(c_i=1\)).

It turns out that with these operations the final circle (and hence the chain) can only be one of a small number of types:

• If n = 2 then the only possibility is the circle [1, 1].
• If n is odd (n > 2) then the only reachable circle (up to rotation) is the one having exactly one yang. Taking all rotations (and noting that a reversal is just a rotation in this case) yields exactly n distinct chains.
• If n is even (n > 2) then there are exactly two reachable circles (up to rotation): one is the circle with all ones, and the other is the circle having exactly two yangs which are adjacent. The all‐ones circle yields only one chain (since all rotations are identical), and the other circle yields n distinct chains.

Your task is to compute the number of distinct chains that satisfy all the given restrictions. Since the answer can be huge, output it modulo \(998244353\).

---

Note on Restrictions and Chains: For a given candidate chain the restrictions are checked as follows. For a candidate chain A[0..n-1] (positions are 0-indexed in your program, but restrictions are given in 1-indexed form):

• For the unique-chain case (when n is odd) the candidate chain is obtained by taking a rotation of the sequence [1, 0, 0, ..., 0] (i.e. exactly one 1 and n-1 zeroes).
• For the 2-case when n is even, one candidate chain is the all-ones sequence [1, 1, ..., 1] and the other comes from rotations of [1, 1, 0, ..., 0] (with the two 1's adjacent).

If any restriction contradicts a candidate chain (for example, if a position is restricted to 0 but the candidate chain has 1 in that position), then that candidate is discarded.

inputFormat

The first line contains two integers n and m (2 ≤ n ≤ 10, 0 ≤ m ≤ n), where n is the final number of spiritual powers and m is the number of restrictions. The next m lines each contain two integers pi and ci (1 ≤ pi ≤ n and ci ∈ {0,1}), meaning that in the chain the pi-th spiritual power must be of type yin if ci=0 or yang if ci=1.

You may assume the restrictions do not conflict with themselves (i.e. for a fixed position, if there is more than one restriction then they all demand the same type).

outputFormat

Output a single integer, which is the number of distinct chains that may be formed and that satisfy all the restrictions, modulo \(998244353\).

sample

2 0

1

</p>