Circular equations

3

5 votes
1-D Array, C++, Combinatorics, Inclusion-exclusion, Math
Problem

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

  • The first line contains an integer Q denoting the number of queries.
  • The next Q lines contain an integer S.

Output format

Print a single integer in a separate line corresponding to each query.

Constraints
1Q1e51S1e18

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

N = 05, 50, 14, 41, 23, 32 satisfy given conditions.

Editor Image

?