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