Row

A string can record a natural number consisting of exactly N digits. You can perform the following operation on this string: cut the string between any two consecutive digits, swap the two resulting parts without reversing them, and then reattach them. A string is deemed "beautiful" if, after this operation, the reattached string still represents the same number. For instance, the number 5656 is beautiful, whereas 5665 is not. Your task is to determine how many different numbers, when written on the string, result in a beautiful string.

Input

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

Output

Output the count of N-digit numbers that make the string "beautiful" modulo 1 000 007.

Examples