eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Одиннадцать

Одиннадцать

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

В этой задаче мы будем ссылаться на цифры целого положительного числа как на последовательность цифр, необходимых для его записи в десятичной системе счисления без ведущих нулей. Например, цифры числа n = 2090 конечно же 2, 0, 9 и 0.

Пусть n - заданное целое положительное число. Назовем натуральное число m одиннадцати-множественно-анаграмматичным числу n, если и только если:

  1. цифры числа m являются перестановкой цифр числа n,

  2. m кратно 11.

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

В качестве примера опять рассмотрим число n = 2090. Значения, которые удовлетворяют первому из условий, приведённых выше, это 2009, 2090, 2900, 9002, 9020 и 9200. Среди них только числа 2090 и 9020 удовлетворяют второму условию, поэтому ответом для n = 2090 является 2.

Вхідні дані

Одна строка, содержащая целое число n (1n 10^100).

Вихідні дані

Выведите единственное целое число, задающее количество одиннадцати-множественно-анаграмматичных чисел для заданного числа n. Так как это число может быть очень большим, выведите остаток от деления его на 10^9 + 7.

Приклад

Вхідні дані #1
201400000000000000000000000000
Вихідні дані #1
0
Автор Pablo Ariel Heiber
Джерело ACM ICPC Regional Latino America 2013