You are given S. Determine the number of possible values of N that satisfy the following condition:
You are given N where represents a number that is generated by shifting the digits of N cyclically towards left by i units.
Also, N must satisfy the provided condition:
S is the summation {F(N,i)} for all i from 0 to |N|−1 where |N| represents the number of digits in N.
N can have leading zeroes. As the number of N can be very large, print it modulo 1000000000+7.
Input format
Output format
Print a single integer in a separate line corresponding to each query.
Constraints
1≤Q≤1e51≤S≤1e18
N = 05, 50, 14, 41, 23, 32 satisfy given conditions.