Description

This problem is a programming version of Problem 31 from projecteuler.net
In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:
1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
It is possible to make £2 in the following way:
1 × £1 + 1 × 50p + 2 × 20p + 1 × 5p + 1 × 2p + 3 × 1p
9
How many different ways can N p be made using any number of coins? As the result can be large print answer mod (10 + 7) Input Format
The first line contains an integer T , i.e., number of test cases.
Next T lines will contain an integer N.
Note: N is given as p and not £
Output Format
Print the values corresponding to each test case.
Constraints
4
1 ≤ T ≤ 10
5
1 ≤ N ≤ 10
Sample Input

Sample Output