Одиннадцать
В этой задаче мы будем ссылаться на цифры целого положительного числа как на последовательность цифр, необходимых для его записи в десятичной системе счисления без ведущих нулей. Например, цифры числа 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.