Одинадцять
У цій задачі ми будемо розглядати цифри цілого додатного числа як послідовність цифр, необхідних для його запису в десятковій системі числення без провідних нулів. Наприклад, цифри числа n = 2090 це 2, 0, 9 і 0.
Нехай n - задане ціле додатне число. Назвемо натуральне число m одинадцяти-множинно-анаграматичним числу n, якщо виконуються наступні умови:
Цифри числа m є перестановкою цифр числа n.
m кратне 11.
Вам потрібно написати програму, яка для заданого числа n обчислює кількість одинадцяти-множинно-анаграматичних чисел.
Розглянемо приклад для числа n = 2090. Значення, які задовольняють першій умові, це 2009, 2090, 2900, 9002, 9020 і 9200. Серед них лише числа 2090 і 9020 задовольняють другій умові, тому відповідь для n = 2090 дорівнює 2.
Вхідні дані
Один рядок, що містить ціле число n (1 ≤ n ≤ 10^100).
Вихідні дані
Виведіть єдине ціле число, яке визначає кількість одинадцяти-множинно-анаграматичних чисел для заданого числа n. Оскільки це число може бути дуже великим, виведіть залишок від ділення його на 10^9 + 7.