Problem Q
Flygildaflug

You have decided to participate in the University of Iceland’s annual drone flying contest. Each contestant in the contest controls a drone and gets points depending on how they fly it. The drone starts on the ground ($y = 0$) at the start line ($x = 0$). The drone can fly up and to the right translating its location by $(1, 1)$. For doing this the contestant gets $m_1y + b_1$ points, where $y$ denotes the height of the drone before the move is performed. The drone can also fly directly to the right translating its location by $(1, 0)$. This moves grants $m_2y + b_2$ points, where $y$ is as before. The drone can finally, assuming it is not at the ground ($y = 0$), fly down and to the right translating its location by $(1, -1)$. This gives $m_3y + b_3$ points, where $y$ is as before. The points for each move that the contestant performs are then multiplied together to get the final score. The final goal is located at $(N, 0)$. The drone has to land at the goal, it does not suffice to fly over it. What is the sum of all possible scores that can be achieved?

Output

The first line of the input contains an integer $1 \leq Q \leq 10^4$. The next line contains three integers $0 \leq m_1, m_2, m_3 \leq 10^9$ and the third line contains three integers $-10^9 \leq b_1, b_2, b_3 \leq 10^9$. Finally there are $Q$ lines, each with one integer $1 \leq N \leq 10^3$.

Input

One line with the sum of all possible flight paths to the goal $(N, 0)$, modulo $10^9 + 7$, for each $N$ in the input.

5
1 2 1
1 1 0
2
3
4
5
6

2
6
24
120
720

5
0 1 1
1 1 0
2
3
4
5
6

2
5
15
52
203

6
1 3 2
1 1 0
2
3
4
5
6
1000

3
13
75
541
4683
581423957