問題文

チェリーちゃんは $28$ 輪の桜を使って, ブーケを作る.

作ろうとしているブーケは $28$ 個のパーツに分かれており, 各パーツにはソメイヨシノまたはサトザクラのうちのどちらか一方の品種のみを $1$ 輪使う.

各パーツについて, 使った桜の品種によって, そのパーツの煌びやかさが決定される. 具体的には, $i=1,2, \dots, 28$ に対して次のようになる.

• $i$ 番目のパーツにソメイヨシノを使った場合, $i$ 番目のパーツの煌びやかさは $G_i$ である.
• $i$ 番目のパーツにサトザクラを使った場合, $i$ 番目のパーツの煌びやかさは $H_i$ である.

また, 完成した $28$ 個パーツのからなるブーケについて, そのブーケの美しさを以下のようにして定める.

• $28$ 個のパーツ全てにおけるの煌びやかさの総和を $M$ で割った余り.

$q=1,2, \dots, Q$ それぞれに対して, 以下の問に答えよ.

• 以下の $2$ 条件を満たすブーケの作り方の数を求めよ.
  • $28$ 個のパーツのうち, ちょうど $K_q$ 個のパーツでソメイヨシノを使う.
  • ブーケの美しさが $X_q$ 以上である.

なお, $2$ つのブーケについて, 一方ではソメイヨシノ, 他方ではサトザクラを使っているようなパーツが存在するとき, そしてその時に限りこの $2$ つのブーケは異なるとする.

制約

• $2 \leq M \leq 10^9$.
• $0 \leq G_i \lt M \quad (1 \leq i \leq 28)$.
• $0 \leq H_i \lt M \quad (1 \leq i \leq 28)$.
• $1 \leq Q \leq 100$.
• 各問に対する制約.
• $0 \leq K_q \leq 28 \quad (1 \leq q \leq Q)$.
• $0 \leq X_q \lt M \quad (1 \leq q \leq Q)$.
• 入力は全て整数.

入力

$M$
$G_1$ $G_2$ $G_3$ $G_4$ $G_5$ $G_6$ $G_7$ $G_8$ $G_9$ $G_{10}$ $G_{11}$ $G_{12}$ $G_{13}$ $G_{14}$ $G_{15}$ $G_{16}$ $G_{17}$ $G_{18}$ $G_{19}$ $G_{20}$ $G_{21}$ $G_{22}$ $G_{23}$ $G_{24}$ $G_{25}$ $G_{26}$ $G_{27}$ $G_{28}$
$H_1$ $H_2$ $H_3$ $H_4$ $H_5$ $H_6$ $H_7$ $H_8$ $H_9$ $H_{10}$ $H_{11}$ $H_{12}$ $H_{13}$ $H_{14}$ $H_{15}$ $H_{16}$ $H_{17}$ $H_{18}$ $H_{19}$ $H_{20}$ $H_{21}$ $H_{22}$ $H_{23}$ $H_{24}$ $H_{25}$ $H_{26}$ $H_{27}$ $H_{28}$
$Q$
$K_1$ $X_1$
$K_2$ $X_2$
$\vdots$
$K_Q$ $X_Q$

出力

出力は $Q$ 行からなる. 第 $q~(1 \leq q \leq Q)$ 行目には $q$ 個目の問に対する解答を整数で出力せよ.

サンプル

46
5 5 5 5 3 3 3 3 3 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2
4 19
18 28

1
6519260

4646
104 1114 1023 215 129 417 418 1012 1219 323 1021 829 112 1013 710 102 928 113 109 725 707 412 217 1108 509 818 215 122
26 25 24 25 22 24 23 24 20 21 25 22 21 24 22 23 18 21 17 19 18 18 20 17 17 19 18 18
3
5 215
6 628
7 1018

95888
325920
816163