Hide

# Problem QFlygildaflug

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.

Sample Input 1 Sample Output 1
5
1 2 1
1 1 0
2
3
4
5
6

2
6
24
120
720

Sample Input 2 Sample Output 2
5
0 1 1
1 1 0
2
3
4
5
6

2
5
15
52
203

Sample Input 3 Sample Output 3
6
1 3 2
1 1 0
2
3
4
5
6
1000

3
13
75
541
4683
581423957