Problem Statement

You are given a positive integer $N$ and a sequence of integers $A = (A_1, A_2, \ldots, A_N)$. Each $A_i$ satisfies $-1 \leq A_i \leq N-1$, and for $1 \leq i < j \leq N$, if $A_i \neq -1$ and $A_j \neq -1$, then $A_i \neq A_j$.

Answer the following query $Q$ times.

• You are given integers $l, r\ (1 \leq l \leq r \leq N)$. Find the sum, modulo $998244353$, of $\mathrm{mex}(\lbrace P_l, P_{l+1}, \ldots, P_r \rbrace)$ over all permutations $P = (P_1, P_2, \ldots, P_N)$ of $(0, 1, \ldots, N-1)$ satisfying $A_i \neq -1 \implies P_i = A_i$.

What is $\mathrm{mex}(S)$? For a set $S$ of non-negative integers, $\mathrm{mex}(S)$ is defined as the smallest non-negative integer not contained in $S$.

Constraints

• $1 \leq N \leq 5000$
• $1 \leq Q \leq 5 \times 10^5$
• $-1 \leq A_i \leq N-1$
• For $1 \leq i < j \leq N$, if $A_i \neq -1$ and $A_j \neq -1$, then $A_i \neq A_j$.
• For each query, $1 \leq l \leq r \leq N$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N Q
A_1 A_2 \ldots A_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Each query is given in the following format:

l r

Output

Output $Q$ lines. The $i$-th line should contain the answer to $\mathrm{query}_i$.