Вам дано целое число $N$ в десятичной записи.
Рассмотрим все целые числа, которые можно получить перестановкой цифр числа $N$ так, чтобы полученное число не содержало ведущих нулей.
Найдите количество таких целых чисел, делящихся на $11$, по модулю простого числа $2147483647$ ($= 2^{31} - 1$).
Обратите внимание, что в число целых чисел, полученных перестановкой цифр числа $N$, входит и само число $N$.
Входные данные
Входные данные даны в следующем формате:
$$N$$
- Все входные значения являются целыми числами.
- $1 \le N < 10^{2 \times 10^6}$
- Число $N$ задано в десятичной записи без ведущих нулей.
Выходные данные
Выведите ответ в единственной строке.
Примеры
Входные данные 1
1001
Выходные данные 1
2
Входные данные 2
31415926535
Выходные данные 2
144000
Примечание
В первом примере условию удовлетворяют числа $1100$ и $1001$.