Petriukas has n tiles, each with a single digit written on it. He forms all possible n! permutations of these tiles. Each permutation represents an n-digit number (leading zeros are allowed).
Petriukas calculates the sum of all these n! numbers and then divides this total sum by the sum of the digits on the n tiles.
What is the result?
Input
In the input, a number A is given, which is an n-digit number where (1 \le n \le 10^3).
Output
Since the result can get very large, print the result modulo 10^9 + 7
Examples
| standard input | standard output |
|---|
| 67
| 11
|