AT_jsc2019_final_f Count Permutations Many Times

有一个长度为 $N$ 的数列 $A_0,A_1,\cdots,A_{N-1}$。请回答接下来的 $Q$ 个询问。 - 第 $i$ 个询问（$0 \leq i < Q$）：给定整数 $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$ 取模的结果。

输入以如下格式从标准输入给出。 > $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 < Q$）输出第 $i$ 个询问的答案，对 $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$ - 所有输入的值均为整数。 ### 样例解释 1 以第 $0$ 个询问为例，满足条件的排列有 $(1,0,2)$、$(1,2,0)$、$(2,0,1)$、$(2,1,0)$ 共 $4$ 种。 由 ChatGPT 4.1 翻译