题目二：

题目背景

在“星港远征计划”中，科研舱需要为一批实验样本分配唯一编号 $0,1,\ldots,N-1$。
不过由于部分记录已经提前锁定，某些舱位上的编号不能改变；还有一些舱位尚未填写，记为 -1。
研究员会不断查询某个连续舱段内样本编号集合的最小缺失值（$\mathrm{mex}$），并希望统计：在所有满足已知记录的完整分配方案中，这个区间的 $\mathrm{mex}$ 总和是多少。

题目描述

给定一个正整数 $N$ 和一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\ldots,A_N)$。

满足：

• $-1 \le A_i \le N-1$
• 对于任意 $1 \le i < j \le N$，如果 $A_i \ne -1$ 且 $A_j \ne -1$，那么 $A_i \ne A_j$

也就是说，所有不等于 $-1$ 的 $A_i$ 两两不同。

接下来有 $Q$ 次询问，每次给出两个整数 $l,r$（$1 \le l \le r \le N$）。

考虑所有满足以下条件的排列 $P=(P_1,P_2,\ldots,P_N)$：

• $P$ 是 $(0,1,\ldots,N-1)$ 的一个排列
• 对于所有 $i$，若 $A_i \ne -1$，则必须有 $P_i=A_i$

对于每个这样的排列，取集合

$$\{P_l,P_{l+1},\ldots,P_r\}$$

并计算它的 $\mathrm{mex}$。

你需要求出：

• 对所有满足条件的排列 $P$
• 上述区间对应的 $\mathrm{mex}$ 值之和
• 并对 $998244353$ 取模

mex 的定义

对于一个由非负整数组成的集合 $S$，$\mathrm{mex}(S)$ 表示最小的没有出现在 $S$ 中的非负整数。

---

输入格式

输入从标准输入给出，格式如下：

N Q
A1 A2 ... AN
l1 r1
l2 r2
...
lQ rQ

---

输出格式

输出 $Q$ 行。

第 $i$ 行输出第 $i$ 次询问的答案。

---

样例 #1

输入

3 4
0 -1 -1
1 1
2 2
1 2
1 3

输出

2
0
3
6

说明

满足条件的排列只有两个：

• $(0,1,2)$
• $(0,2,1)$

因此：

• 询问 $(1,1)$：$\mathrm{mex}(\{0\})+\mathrm{mex}(\{0\})=1+1=2$
• 询问 $(2,2)$：$\mathrm{mex}(\{1\})+\mathrm{mex}(\{2\})=0+0=0$
• 询问 $(1,2)$：$\mathrm{mex}(\{0,1\})+\mathrm{mex}(\{0,2\})=2+1=3$
• 询问 $(1,3)$：$\mathrm{mex}(\{0,1,2\})+\mathrm{mex}(\{0,2,1\})=3+3=6$

---

样例 #2

输入

5 3
-1 2 -1 -1 1
1 4
3 5
1 5

输出

6
8
30

---

样例 #3

输入

15 1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
1 15

输出

612227903

---

数据范围

• $1 \le N \le 5000$
• $1 \le Q \le 5 \times 10^5$
• $-1 \le A_i \le N-1$
• 对于任意 $1 \le i < j \le N$，如果 $A_i \ne -1$ 且 $A_j \ne -1$，那么 $A_i \ne A_j$
• 每次询问满足 $1 \le l \le r \le N$
• 输入中的所有值均为整数