Problem A
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_{1}y+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_{2}y+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_{3}y+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\le Q\le {10}^4$. Næsta lína inniheldur þrjár heiltölur $0\le m_1,m_2,m_3\le {10}^9$ og þriðja línan inniheldur þrjár heiltölur $-{10}^9\le b_1,b_2,b_3\le {10}^9$. Loks koma $Q$ línur, hver með einni heiltölu $1\le N\le {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