Sum is X, Min is Y

2 secs 1024 MB
magurofly

問題文


非負整数からなる集合 が与えられます。

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

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

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

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

制約


  • 入力はすべて整数である

入力


出力


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

入出力例


入力例1
3 3
1 10 100
11 1
111 1
10 1
出力例1
1
1
0
  • 和が 、最小値が になる部分集合には があります。
  • 和が 、最小値が になる部分集合には があります。
  • 和が 、最小値が になる部分集合は存在しません。
入力例2
5 3
1 2 3 4 5
6 1
10 1
10 2
出力例2
2
2
1
  • 和が 、最小値が になる部分集合には があります。
  • 和が 、最小値が になる部分集合には があります。
  • 和が 、最小値が になる部分集合には があります。
入力例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

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

提出


Go (1.14)