У цій задачі ми будемо розглядати цифри цілого додатного числа як послідовність цифр, необхідних для його запису в десятковій системі числення без провідних нулів. Наприклад, цифри числа = це , , і .
Нехай - задане ціле додатне число. Назвемо натуральне число одинадцяти-множинно-анаграматичним числу , якщо виконуються наступні умови:
Цифри числа є перестановкою цифр числа .
кратне .
Вам потрібно написати програму, яка для заданого числа обчислює кількість одинадцяти-множинно-анаграматичних чисел.
Розглянемо приклад для числа = . Значення, які задовольняють першій умові, це , , , , і . Серед них лише числа і задовольняють другій умові, тому відповідь для = дорівнює .
Один рядок, що містить ціле число ( ≤ ≤ 10^{100}).
Виведіть єдине ціле число, яке визначає кількість одинадцяти-множинно-анаграматичних чисел для заданого числа . Оскільки це число може бути дуже великим, виведіть залишок від ділення його на 10^9 + 7.
Приклад 1