# Problem Q

Flygildaflug

Languages
en
is
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 |