Одинадцять#6585

Одинадцять

1 секунда
64 мегабайти
Дуже легка

У цій задачі ми будемо розглядати цифри цілого додатного числа як послідовність цифр, необхідних для його запису в десятковій системі числення без провідних нулів. Наприклад, цифри числа = це , , і .

Нехай - задане ціле додатне число. Назвемо натуральне число одинадцяти-множинно-анаграматичним числу , якщо виконуються наступні умови:

  1. Цифри числа є перестановкою цифр числа .

  2. кратне .

Вам потрібно написати програму, яка для заданого числа обчислює кількість одинадцяти-множинно-анаграматичних чисел.

Розглянемо приклад для числа = . Значення, які задовольняють першій умові, це , , , , і . Серед них лише числа і задовольняють другій умові, тому відповідь для = дорівнює .

Вхідні дані

Один рядок, що містить ціле число ( ≤ ≤ 10^{100}).

Вихідні дані

Виведіть єдине ціле число, яке визначає кількість одинадцяти-множинно-анаграматичних чисел для заданого числа . Оскільки це число може бути дуже великим, виведіть залишок від ділення його на 10^9 + 7.

Приклади

Приклад 1

Loading
Loading