In this problem, we refer to the digits of a positive integer as the sequence of digits required to write it in base without leading zeros. For instance, the digits of = are of course , , and .
Let be a positive integer. We call a positive integer an eleven-multiple-anagram of if and only if
the digits of are a permutation of the digits of , and
is a multiple of .
You are required to write a program that given , calculates the number of its eleven-multiple-anagrams.
As an example, consider again = . The values that meet the first condition above are , , , , and . Among those, only and satisfy the second condition, so the answer for = is .
One integer ( ≤ ≤ 10^{100}).
Print a line with an integer representing the number of eleven-multiple-anagrams of . Because this number can be very large, you are required to output the remainder of dividing it by 10^9 + 7.
Shembulli 1