Prefix Permutation

問題文

長さ $N$ の順列 $p=(p_1,p_2,\ldots,p_N)$ のうち、以下の条件を満たすものの個数を $998244353$ で割った余りを求めてください。

• $1 \leq i \leq M$ を満たす全ての整数 $i$ について、 $p_1+p_2+\ldots +p_{a_i}$ を $2$ で割った余りが $b_i$ である。

制約

• $1\leq N \leq 2000$
• $0\leq M \leq 2×N$
• $1\leq a_i \leq N$
• $0\leq b_i \leq 1$
• $i≠j$ ならば $(a_i,b_i)≠(a_j,b_j)$
• 入力は全て整数 　　

入力

入力は以下の形式で標準入力から与えられます。

出力

答えを出力してください。

入力例1

3 1
2 0

出力例1

2

$(1,3,2)$ と $(3,1,2)$ の $2$ つが条件を満たします。

入力例2

6 2
1 0
1 1

出力例2

0

$i≠j$ ならば $(a_i,b_i)≠(a_j,b_j)$ ですが、 $a_i≠a_j$ とは限りません。

入力例3

1000 0

出力例3

421678599

$998244353$ で割った余りを求めることに注意してください。