問題文
非負整数からなる集合 A={A1,A2,…,AN} が与えられます。
Q 個のクエリに答えてください。
j 番目のクエリでは、 A の空でない部分集合のうち、以下のどちらの条件も満たすものの個数を求めてください。
- 全ての要素の総和を 1009 で割ったあまりが Xj
- 最小の要素が Yj
ただし、答えは非常に大きくなることがあるため、 998244353 で割ったあまりを出力してください。
制約
- 1≤N≤1000
- 0≤Ai<1009
- i=j→Ai=Aj
- 1≤Q≤105
- 0≤Xj<1009
- Yj∈A
- 入力はすべて整数である
入力
出力
各クエリ毎に答えを 1 行、合計 Q 行出力せよ。
入出力例
入力例1
3 3
1 10 100
11 1
111 1
10 1
- 和が 11 、最小値が 1 になる部分集合には {1,10} があります。
- 和が 111 、最小値が 10 になる部分集合には {1,10,100} があります。
- 和が 10 、最小値が 1 になる部分集合は存在しません。
入力例2
5 3
1 2 3 4 5
6 1
10 1
10 2
- 和が 6 、最小値が 1 になる部分集合には {1,2,3},{1,5} があります。
- 和が 10 、最小値が 1 になる部分集合には {1,2,3,4},{1,4,5} があります。
- 和が 10 、最小値が 2 になる部分集合には {2,3,5} があります。
入力例3
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
出力例3
459533214
205011665
724447665
318565923
636127576
998244353 で割ったあまりを出力することに注意してください。