G. Sum of Binomial Coefficients

Problem Description

Given an increasing sequence $A$ of length $m$. There are $q$ queries, each given $N, R$, calculate:

$$\left(\sum_{i=1}^R \binom{N}{A_i}\right) \bmod {998244353}$$

Input

The first line of the input contains two integers $m, q$ ($1 \le m, q < 2 ^ {17}$) - the length of $A$ and the number of queries. The second line contains $m$ integers $A_1, A_2, \dots, A_m$ ($1 \le A_1 < A_2 < \dots < A_m < 2 ^ {17}$). Each of the following $q$ lines contains two integers $N, R$ ($1 \le N \le 10 ^ 9$, $1 \le R \le m$).

Output

For each query, print a single integer - the answer of the query, modulo $998244353$.

Sample Input

6 10
2 4 5 6 8 10
5 2
5 1
4 3
8 5
5 2
5 1
10 6
7 6
6 2
8 6

Sample Output

15
10
7
183
15
10
763
84
30
183

Hint

There is a template for polynomial operations in this link.

Source

2023“钉耙编程”中国大学生算法设计超级联赛（7）