小 Y 最近学会了如何用线段树维护序列,并支持区间求和的操作。
以下给出本题中线段树的定义。该定义可能和你熟知的线段树有区别。
- 线段树是一种有根的二叉树,其每个节点对应了序列上的一个区间 [l,r),其中根节点对应 [0,n)。
- 对于每个节点,若其代表的序列区间 [l,r) 满足 r−l=1,则其为叶节点;否则存在整数 m(l<m<r),满足其左儿子代表区间 [l,m),右儿子代表区间 [m,r)。
- 可以注意到,线段树的形态取决于每个非叶结点的划分点 m 的选择。
- 在区间求和的问题上,对于序列 a0,a1,…,an−1,线段树的每个结点 [l,r) 维护了 (al+al+1+⋯+ar−1) 的值。
小 J 有一个长度为 N 的数组 A0,A1,…,AN−1,他并不知道 A 中的任何一个数,但是他有一棵线段树维护了 A 的区间和。线段树由 X1,X2,…,XN−1 给出,其中 Xi 是线段树先序遍历的第 i 个非叶结点的划分点。例如,如果 N=5,X=[2,1,4,3],则线段树包含的结点的先序遍历为 [0,5),[0,2),[0,1),[1,2),[2,5),[2,4),[2,3),[3,4),[4,5)。
小 J 有 M 个区间 [L1,R1),[L2,R2),…,[LM,RM),他想知道,在所有 22N−1 个线段树结点的子集中,有多少个子集 S 满足以下条件:
- 如果已知 S 中所有结点维护的值,则每个 [Li,Ri) 区间的和都能被唯一确定。
例如,如果已知 [0,1),[1,2),就能确定 [0,2) 的和;反过来,如果已知 [0,1),[0,2),也能确定 [1,2) 的和。但如果仅已知 [0,2),[2,4) 则不能确定 [0,3) 或 [1,2) 的和。
由于答案很大,你需要输出答案对 998,244,353 取模后的值。
输入格式
从标准输入读入数据。
输入的第一行两个整数 N,M。
第二行 N−1 个整数 X1,X2,⋯,XN−1。
接下来 M 行,每行两个整数 Li,Ri。
输出格式
输出到标准输出。
输出一行一个整数表示答案对 998,244,353 取模后的值。
样例
输入
2 1
1
0 2
输出
5
解释
只有当直接知道 [0,2) 的总和或同时知道 [0,1) 和 [1,2) 的总和时才能知道 [0,2) 的总和,因此总的方案数为 22+1=5。
样例
输入
2 1
1
1 2
输出
5
样例
输入
5 2
2 1 4 3
1 3
2 5
输出
193
样例
输入
10 10
5 2 1 3 4 7 6 8 9
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10
输出
70848
该组数据满足特殊性质。
子任务
对于所有测试数据,
- 2≤N≤2×105,
- 1≤M≤min,
- \forall 1 \le i \le N-1, 1\le X_i\le N-1,
- 保证 X_i 正确描述了一棵线段树,
- \forall 1 \le i \le M, 0\le L_i < R_i \le N,
- \forall i \ne j, (L_i,R_i)\ne (L_j,R_j)。
子任务 1(6 分):N\le 10。
子任务 2(18 分):N\le 100。
子任务 3(9 分):N\le 500。
子任务 4(17 分):N\le 5\,000。
子任务 5(10 分):M=1。
子任务 6(13 分):M\le 5。
子任务 7(7 分):M=N,L_i=0,R_i=i。
子任务 8(20 分):无额外限制。