To the north of the wall, Mance rayder is gathering an army of wildings and giants to attack on the wall. Given at the starting (at day 0) there are 100 wildings and 10 giants and every day corresponding to every old wilding, 2 new wildlings join the army and every alternate days corresponding to every old giant, a new giant joins the army. In the fight, a crow (man of the night's watch) can kill 3 wildlings and 4 crows are required to kill a giant. Given the number of days after which Mance Rayder will attack on the wall, find out the total number of crows required to win the battle on the wall.

Note: Mance Rayder is considered as wildling and is included in the starting 100.

INPUT

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. Each test case will contain a single number N, the number of days after which Mance Rayder attacks on the wall.

OUTPUT

For each test case, output the number of crows required to defend the wall. As the number can be very large, output answer after taking modulus 10^9+7

Constraints

0 < T <= 100
0 <= N <= 10^9