Problem Q
Flygildaflug

Þú hefur ákveðið að taka þátt í árlegu flygildaflugskeppni Háskóla Íslands. Í þessarri keppni stjórnar hver keppandi flygildi og fær stig útfrá frammistöðu sinni við það verk. Flygildið byrjar á jörðinni ($y = 0$) og við upphafslínu ($x = 0$). Á hverjum tímapunkti er hægt að láta flygildið fljúga upp og áfram sem hliðrar staðsetningu þess um $(1, 1)$. Við þetta fær keppandi $m_1y + b_1$ stig þar sem $y$ er hæð flygildisins frá jörðu í upphafi þessarar hreyfingar. Einnig getur flygildið flogið beint áfram sem hliðrar staðsetningu þess um $(1, 0)$. Við þetta fær keppandi $m_2y + b_2$ stig þar sem $y$ er áfram það sama. Loks ef flygildið er ekki þegar niður við jörðu ($y = 0$) getur flygildið flogið niður á við og áfram sem hliðrar staðsetningu þess um $(1, -1)$. Þetta gefur $m_3y + b_3$ stig þar sem $y$ merkir enn það sama. Athugið að stig keppanda eru margföldið saman fyrir eitt flug frekar en að þau séu lögð saman. Á hnitinu $(N, 0)$ er markið og keppendur verða að lenda á jörðinni í marki, ekki dugar að fljúga yfir. Hver er summa stiganna sem hægt er að fá fyrir allar mögulegar flugleiðir í þetta gefna mark?

Inntak

Fyrsta lína inntaksins inniheldur eina heiltölu $1 \leq Q \leq 10^4$. Næsta lína inniheldur þrjár heiltölur $0 \leq m_1, m_2, m_3 \leq 10^9$ og þriðja línan inniheldur þrjár heiltölur $-10^9 \leq b_1, b_2, b_3 \leq 10^9$. Loks koma $Q$ línur, hver með einni heiltölu $1 \leq N \leq 10^3$.

Úttak

Eina línu með summu stiganna yfir allar mögulegar flugleiðir í markið $(N, 0)$ mátað við $10^9 + 7$ fyrir hverja tölu $N$ í inntakinu.

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