URI Online Judge | 3008

Matches Numbers

By Paulo E. D. Pinto, Universidade do Estado do Rio de Janeiro BR Brazil

Timelimit: 3

Positive decimal integers can be well represented with matchsticks using the following scheme for each digit:

UOJ_3008

Raphael has a lot of matches sticks and wonders how many different numbers he can form using all the sticks he has. For example, with 8 sticks, he can form 19 different numbers: 10, 16, 19, 27, 37, 44, 57, 61, 72, 73, 75, 91, 114, 141, 177, 411, 717, 771, 1111. Note that setting 01 is not valid, as 0s on the left should not be represented. He realized this number can be very large. So he asks your help with a program to find the answer he wants.

Input

The input consists of many tests. The first line contains the number of test cases, an integer n (1 ≤ n ≤ 100),  The next n lines contain, each one, a test case, which consists of a unique integer q (0 ≤ q ≤ 10000), that indicates the number of matches sticks that Raphael has.

Output

For each test case, print on one line the number of distinct integers Raphael can form. Since this value can be very large, print the value in module 1000007.

Input Sample Output Sample

5

1

8

15

100

5000

0

19

854

964359

286298