A string can represent a natural number consisting of exactly digits. The following operation can be performed on this string: you may cut the string between any two consecutive digits, swap the two resulting parts without reversing them, and then reattach them. The string is called beautiful if, after this operation, the string still represents the same number. For example, the number is beautiful, while is not. Determine how many different numbers, when written on the string, make it beautiful.
The input consists of a single integer: the length of the string . 1 \leq N \leq 1\ 000\ 007.
Output the number of -digit numbers making the string beautiful, modulo .
Example 1