Вам дано ціле число $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$.