「Wdsr-2」阴阳玉
题目背景
博丽灵梦有一块好大好大的阴阳玉,它是是博丽灵梦的主要武器之一。
但是阴阳玉的能量来源,源自主人的灵力聚集力量,因此,灵梦在平时总是需要对其进行保养。简单来说,灵梦会使用灵力,来获取阴阳玉所需的能量。
题目描述
灵力有阴阳之分。初始的时候,灵梦只有两个阳灵力,它们围成了一个圈。每次,灵梦可以进行以下两种操作:
- 在两个灵力直接加入一个阳灵力。
- 移走一个阳灵力。
为了保持稳定,任何时候这个圈上的灵力都**不应该少于两个**。
由于灵力的阴阳并不稳定,因此一旦某个灵力周围发生改变(多出一个灵力,或减少一个灵力),它就会从阳变成阴,或从阴变成阳。不过,如果只是周边灵力的性质改变,那么它就不会发生变化。
灵梦会不断调节灵力,直到它**最终**变成 $n$ 个(中途可能多于 $n$ 个)。然后,灵梦会从某个点**依次**按照顺时针或逆时针取下每个灵力。它会形成一条链。灵梦会用链上的能量,来加强她的阴阳玉。
做到这一点非常容易。但是灵梦非常好奇,一共可能形成多少种不同的**链**。
由于灵梦的偏好,她可能会有 $m$ 个限制条件。第 $i$ 个条件 $(p_i,c_i)$ ,规定了链上第 $p_i$ 个灵力应该为何种灵力。若 $c_i=0$ ,则应该为阴灵力;否则为阳。
由于可能结果太大,灵梦只需要得到答案对 $998244353$ 取模的结果。
两个链不同,当且仅当存在一个位置的点颜色不同。
输入输出格式
输入格式
第一行为一个正整数 $n$ 和一个非负整数 $m$ 。
当 $m=0$ 时无约束条件。否则接下来会有 $m$ 行,每行两个非负整数 $p_i,c_i$ ,含义如上。
输出格式
一行,一个非负整数,表示所有链的可能种类总数对 $998244353$ 取模的值。
输入输出样例
输入样例 #1
4 0
输出样例 #1
5
输入样例 #2
4 1
1 1
输出样例 #2
3
输入样例 #3
20 10
5 1
12 0
17 0
3 1
7 1
13 0
8 1
18 1
2 1
19 0
输出样例 #3
344
说明
#### 样例解释
对于样例一,可能存在以下两种构造方式:
![pic3.JPG/The "2"-th of the "1"-st.](https://i.loli.net/2020/07/17/VQn8MB7fxJsA1Rr.jpg)
其中, $\tt ADD$ 表示增加一个阳灵力,$\tt RMV$ 表示移走一个阳灵力。
将得到的两个环分别拆开,一共可以得到以下五种链:
- 环一:**阳—阳—阳—阳**。
- 环二:**阳—阳—阴—阴**,**阳—阴—阴—阳**,**阴—阴—阳—阳**,**阴—阳—阳—阴**。
因此答案为 $5$ 。
对于样例二,我们限定了链上第一个灵力为阳。因此结果为 $3$ 。
#### 数据范围
$$\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}$$
此外,对于全部数据,有 $1\le p_i\le n,c_i\in \{0,1\}, 0\le m\le n$ 且 $p_i$ 各不相同。