Matches Numbers
By Paulo E. D. Pinto, Universidade do Estado do Rio de Janeiro 
Brazil
By Paulo E. D. Pinto, Universidade do Estado do Rio de Janeiro Brazil
Positive decimal integers can be well represented with matchsticks using the following scheme for each digit:
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.
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.
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 |