Problems
Результативность перестановок
Результативность перестановок
Для заданной последовательности неотрицательных целых чисел определить количество различных последовательностей, полученных из последовательности десятиричных цифр этих чисел, выписанных в порядке следования, всевозможными перестановками, включая начальную последовательность цифр. Ответ выдать по модулю \textbf{1000000009}.
Общее количество цифр не превосходит \textbf{1000}.
\InputFile
В единственной строке заданная последовательность чисел (через пробелы).
\OutputFile
В единственной строке -- ответ задачи.
Input example #1
1 2 4 3
Output example #1
24