eolymp
bolt
Try our new interface for solving problems
Problems

Eleven

Eleven

Time limit 1 second
Memory limit 64 MiB

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 data

One integer n (1 n 10^100).

Output data

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

Input example #1
201400000000000000000000000000
Output example #1
0
Author Pablo Ariel Heiber
Source ACM ICPC Regional Latino America 2013