配点 : 800 点
問題文
长度 一名打着 N 序列 由 A_0,A_1,\cdots,A_{N-1} 。 下一个 请回答 Q 问题。 给出
- 質問 i (0 \leq i \leq Q-1): 整数 L_i,R_i (0 \leq L_i < R_i \leq N)。
找出满足以下条件的
(0,1,\cdots,N-1) 的排列
选择 p_0,p_1,\cdots,p_{N-1} 的数量。
- 全部 j (L_i \leq j < R_i),p_j \neq A_j 。
然而,答案可能非常大,所以 请打印除以998244353 后的余数。
制約
- 1 \leq N \leq 2000
- 0 \leq A_i \leq N-1
- 1 \leq Q \leq 2000
- 0 \leq L_i < R_i \leq N
- 所有输入值都是整数。 输出
入力
输入是按以下格式从标准输入给出的。
N Q
A_0 A_1 \cdots A_{N-1}
L_0 R_0
L_1 R_1
\vdots
L_{Q-1} R_{Q-1}
出力
Q 行。 i+1 (0 \leq i \leq Q-1) 行包含问题 i 的答案 打印除以 998244353 后的余数。
入力例 1
3 6 0 0 0 0 1 0 2 0 3 1 2 1 3 2 3
出力例 1
4 2 0 4 2 4
例如,问题 考虑 0 ,满足条件的排列是 (1,0,2),(1,2,0),(2,0,1),(2,1,0) 的 4 没错。
入力例 2
3 6 0 1 2 0 1 0 2 0 3 1 2 1 3 2 3
出力例 2
4 3 2 4 3 4
入力例 3
10 10 7 9 4 8 0 6 7 8 9 8 0 5 4 7 3 10 7 10 7 9 4 9 0 3 6 9 4 9 1 3
出力例 3
2170680 2656080 1712520 2620800 2943360 2170680 2656080 2656080 2170680 2943360