Problem Description

There is a sequence of length $ N $: $A_0, A_1, \cdots, A_{N-1}$. Answer the following $ Q $ queries:

• Query $ i $ ($0 \leq i \leq Q-1$): Given integers $ L_i, R_i $ ($0 \leq L_i < R_i \leq N$). Find the number of permutations $p_0, p_1, \cdots, p_{N-1}$ of $(0, 1, \cdots, N-1)$ that satisfy the following condition:
• For all $ j $ ($L_i \leq j < R_i$), $p_j \neq A_j$.

Since the answer can be very large, output it modulo $ 998244353 $.

Input Format

The input is given from the standard input in the following format:

$ 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} $

Output Format

Output $ Q $ lines. The $ i+1 $ ($0 \leq i \leq Q-1$) line should contain the answer to query $ i $ modulo $ 998244353 $.

Sample Input and Output

Sample Input #1

3 6
0 0 0
0 1
0 2
0 3
1 2
1 3
2 3

Sample Output #1

4
2
0
4
2
4

Sample Input #2

3 6
0 1 2
0 1
0 2
0 3
1 2
1 3
2 3

Sample Output #2

4
3
2
4
3
4

Sample Input #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

Sample Output #3

2170680
2656080
1712520
2620800
2943360
2170680
2656080
2656080
2170680
2943360

Notes/Hints

Constraints

• $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$
• All values inputted are integers.

Sample Explanation 1

For example, considering query $ 0 $, the permutations that satisfy the condition are $ (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0) $, which are $ 4 $ in total.

见题面 Input 部分

见题面 Output 部分