Problem Statement

A certain mysterious pocket contains red biscuits and green biscuits, $1$ of each.

The curious Koa has decided to hit this pocket $T$ times.
When the pocket is hit for the $t$-th $(1 \leq t \leq T)$ time, the colors and numbers of the biscuits change as follows.

• If $t$ is odd, for every $1$ red biscuit, $A$ blue biscuits are newly added to the pocket, and for every $1$ green biscuit, $B$ blue biscuits are newly added to the pocket.

• If $t$ is even, all green biscuits vanish, then all red biscuits turn into green biscuits,
  and after that, all blue biscuits turn into red biscuits.

You are given $N$ integer values $T_{1},T_{2}, \dots ,T_{N}$.

For each $i$ $(1 \leq i \leq N)$, find the total number of biscuits in the pocket after hitting it $T_{i}$ times, modulo $10^{9}+7$.

Constraints

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

• $1 \leq N \leq 1000$

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

• All inputs are integers.

Input

The input is given in the following format.

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

• Line $1$ contains $A$ and $B$ in this order, separated by a single-byte space.

• Line $2$ contains $N$.

• Line $(2+i)$ $(1 \leq i \leq N)$ contains $T_{i}$.

Output

Print the answers, $1$ per line, for a total of $N$ lines, followed by a newline at the end.

On line $i$ $(1 \leq i \leq N)$, print the total number of biscuits in the pocket after hitting it $T_{i}$ times, modulo $10^{9}+7$.

Sample

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