Effectiveness of Permutations

Given a sequence of non-negative integers, determine how many distinct sequences can be formed by permuting the sequence of their decimal digits, including the original sequence. Provide the result modulo 1000000009.

The total number of digits will not exceed 1000.

Input

A single line containing the sequence of numbers, separated by spaces.

Output

A single line containing the answer to the problem.

Examples