Given S, find the count of possible values of N which satisfy below condition:

Given N, F(N,i) represent a number which is generated by shifting the digits of N cyclically towards left by i units.

N must satisfy given condition:
S = Summation { F(N,i) } for all i from 0 to |N| - 1 , where |N| represent number of digits in N.

N can have leading zeroes. As the number of N can be very large output it modulo 1000000000 + 7.

Input :
1. First line contain an integer Q, denoting number of queries.
2. Next Q lines contain an integer S.

Output :
Print a single integer in separate line corresponding to each Query.

Constraint  :
1 <= Q <= 1e5
1 <= S <= 1e18