403173: GYM101061 B RGB plants

Farmer John has recently bought three flowers in order to plant them around his house. The flowers were of three different colors red, green and blue.

As we all know, the garden that surrounds farmer John's house is a magical garden. That means that if you plant a number of flowers in it on some day, then the number of flowers will increase in the next day.

The garden increases the number of flowers depending on the color of the flowers, that is, if you plant a red flower in a day, then it will turn into 6 flowers in the next day (1 red flower, 2 green flowers, and 3 blue flowers). If you plant a green flower in a day, then it will turn into 15 flowers in the next day (4 red flowers, 5 green flowers, and 6 blue flowers). If you plant a blue flower in a day, then it will turn into 24 flowers in the next day (7 red flowers, 8 green flowers, and 9 blue flowers).

As we have mentioned above, farmer John has three flowers (1 red flower, 1 green flower, and 1 blue flower), and he will plant them in his magical garden around his house, so the number of the flowers will increase over time. Farmer John knows that if he plants his three flowers in his magical garden, then the number of flowers will increase from day to day, so he wants to know the total number of flowers in his magical garden in the n^th day.

The first line of the input is the number of test cases T (1 ≤ T ≤ 10³). Each test case consists of a single line containing a single integer n (1 ≤ n ≤ 10⁹).

For each test case, print a single line containing the total number of flowers in the magical garden in the n^th day modulo 1000000007.

4
1
2
20
1000000

3
45
238775645
464884429