Eleven

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 he answer for n = 2090 is 2.

Input

One integer n (1 ≤ n ≤ 10^100).

Output

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 10^9 + 7.

Examples