Row#767

Row

1 second
64 megabytes
Hard

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.

Input

The input consists of a single integer: the length of the string . 1 \leq N \leq 1\ 000\ 007.

Output

Output the number of -digit numbers making the string beautiful, modulo .

Examples

Example 1

Loading
Loading