問題文

非負整数からなる集合 $A = \{A_1, A_2, \ldots, A_N\}$ が与えられます。

$Q$ 個のクエリに答えてください。

$j$ 番目のクエリでは、 $A$ の空でない部分集合のうち、以下のどちらの条件も満たすものの個数を求めてください。

• 全ての要素の総和を $1009$ で割ったあまりが $X_j$
• 最小の要素が $Y_j$

ただし、答えは非常に大きくなることがあるため、 $998244353$ で割ったあまりを出力してください。

制約

• $1 \le N \le 1000$
• $0 \le A_i \lt 1009$
• $i \ne j \to A_i \ne A_j$
• $1 \le Q \le 10^5$
• $0 \le X_j \lt 1009$
• $Y_j \in A$
• 入力はすべて整数である

入力

出力

各クエリ毎に答えを $1$ 行、合計 $Q$ 行出力せよ。

入出力例

3 3
1 10 100
11 1
111 1
10 1

1
1
0

• 和が $11$ 、最小値が $1$ になる部分集合には $\{1, 10\}$ があります。
• 和が $111$ 、最小値が $10$ になる部分集合には $\{1, 10, 100\}$ があります。
• 和が $10$ 、最小値が $1$ になる部分集合は存在しません。

5 3
1 2 3 4 5
6 1
10 1
10 2

2
2
1

• 和が $6$ 、最小値が $1$ になる部分集合には $\{1, 2, 3\}, \{1, 5\}$ があります。
• 和が $10$ 、最小値が $1$ になる部分集合には $\{1, 2, 3, 4\}, \{1, 4, 5\}$ があります。
• 和が $10$ 、最小値が $2$ になる部分集合には $\{2, 3, 5\}$ があります。

50 5
0 3 33 28 21 39 18 17 10 32 12 40 36 49 15 25 45 27 50 8 22 52 56 38 59 53 55 30 9 47 24 20 11 46 4 7 35 41 54 6 16 34 23 29 48 43 13 31 44 5
146 0
177 4
70 3
165 4
64 0

459533214
205011665
724447665
318565923
636127576

$998244353$ で割ったあまりを出力することに注意してください。