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 file contains several test cases, each of them as described below. A single line that contains an integer N (1 ≤ N ≤ 10100). Output For each test case, output 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 2090 16510 201400000000000000000000000000 Sample Output 2 12 0