問題文

ある不思議なポケットに赤色ビスケットと緑色ビスケットが $1$ 個ずつ入っています。

好奇心旺盛なコアさんは、このポケットを $T$ 回叩くことにしました。
ポケットを $t$ $(1 \leq t \leq T)$ 回目に叩いたとき、ビスケットの色と数が次のように変化します。

• $t$ が奇数のとき、赤色ビスケット $1$ 個につき $A$ 個、緑色ビスケット $1$ 個につき $B$ 個の青色ビスケットが新たにポケット内に追加される。

• $t$ が偶数のとき、緑色ビスケットがすべて消滅した後、赤色ビスケットがすべて緑色ビスケットに変化し、
  その後、青色ビスケットがすべて赤色ビスケットに変化する。

$N$ 個の整数値 $T_{1},T_{2}, \dots ,T_{N}$ が与えられます。

各 $i$ $(1 \leq i \leq N)$ ごとに、$T_{i}$ 回叩いた後のポケット内に存在するビスケットの総数を $10^{9}+7$ で割った余りを求めてください。

制約

• $1 \leq A,B \leq 10^{9}$

• $1 \leq N \leq 1000$

• $0 \leq T_{i} \leq 10^{18}$ $(1 \leq i \leq N)$

• 入力はすべて整数

入力

入力は次の形式で与えられます。

$A$ $B$
$N$
$T_{1}$
$T_{2}$
 $\vdots$
$T_{N}$

• $1$ 行目には $A$ と $B$ がこの順に半角スペース区切りで与えられる

• $2$ 行目には $N$ が与えられる

• $(2+i)$ $(1 \leq i \leq N)$ 行目には $T_{i}$ が与えられる

出力

答えを $1$ 行ずつ合計 $N$ 行に出力し、最後に改行してください。

$i$ $(1 \leq i \leq N)$ 行目には、$T_{i}$ 回叩いた後のポケット内に存在するビスケットの総数を $10^{9}+7$ で割った余りを出力してください。

サンプル

3 2
5
0
1
2
3
4

2
7
6
23
22

1 2
10
3
50
327362983
5271559
19
8467387694249466
10704815128332
2578440
758998
5041

9
67108864
331052732
465750649
2389
265767032
562491267
423879848
257896762
389805843