当前没有测试数据。

题目描述

有一个长度为 $N$ 的序列 $a$， 对于 $Q$ 个区间 $l, r$， 求

对 $998244353$ 取模后的结果。

输入格式

第一行两个正整数 $N, Q$。含义如题面所示。

第二行 $N$ 个数，第 $i$ 个数为 $a_i$。

接下来 $Q$ 行，每行两个正整数 $l, r$。

输出格式

对于每一对 $l, r$，给出相应的答案，中间用换行隔开。

输入输出样例 #1

输入 #1

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

输出 #1

2
20
120

输入输出样例 #2

输入 #2

5 3
1 2 0 4 5
1 2
4 5
1 5

输出 #2

2
20
0

数据规模及约定

对于 $30\%$ 的数据，保证 $1 \le N, Q \le 10, 1 \le a_i \le 5$。

对于 $100\%$ 的数据，保证 $1 \le l \le r \le N, 1 \le N, Q \le 10^6, \textbf{0} \le a_i \le 10$。