URI Online Judge | 1494

Eleven

By Pablo Ariel Heiber Argentina
Timelimit: 5

In this problem, we refer to the digits of a positive integer as the sequence of digits required to write it in base 10 without leading zeros. For instance, the digits of N = 2090 are of course 2, 0, 9 and 0. Let N be a positive integer. We call a positive integer M an eleven-multiple-anagram of N if and only if (1) the digits of M are a permutation of the digits of N, and (2) M is a multiple of 11. You are required to write a program that given N, calculates the number of its eleven-multiple-anagrams. As an example, consider again N = 2090. The values that meet the first condition above are 2009, 2090, 2900, 9002, 9020 and 9200. Among those, only 2090 and 9020 satisfy the second condition, so the answer for N = 2090 is 2.

Input

The input consists of many test cases and ends with EOF. Each test case is composed by a single line that contains an integer N (1 <= N <= 10^100).

Output

For each test case, print a line with an integer representing the number of eleven-multiple-anagrams of N. Because this number can be very large, you are required to output the remainder of dividing it by 109 + 7.

Sample Input Sample Output

2090
16510
201400000000000000000000000000
 

2
12
0