You are given an integer $N$ represented in decimal.
Consider all integers that can be formed by rearranging the digits of $N$ such that the resulting number has no leading zeros.
Find the number of such integers that are divisible by $11$, modulo $2147483647$ ($= 2^{31} - 1$), which is prime.
Note that the integers formed by rearranging the digits of $N$ include $N$ itself.
Input
The input is given in the following format:
$$N$$
- All input values are integers.
- $1 \le N < 10^{2 \times 10^6}$
- $N$ is given in decimal without leading zeros.
Output
Print the answer on a single line.
Examples
Input 1
1001
Output 1
2
Input 2
31415926535
Output 2
144000
Note
In the first example, $1100$ and $1001$ satisfy the condition.