Supervin likes counting. In this problem, he invites you to count together.

Supervin defines a word as "a string only consist of 'o' or 'x'", and additional requirement, for each substring with prime-length, the number of 'o' is not less than the number of 'x'.

Supervin gives you an integer N (1 <= N <= 10^12). Supervin challenges you to determine how many words can be made with exactly N-length.

You are having difficulties, make a program to determine how many N-length words. Because the output can be too big, output the number of words modulo 1 000 000 007.

Input

One line, an integer N

Output

One line, an integer indicates how many N-length words modulo 1 000 000 007

Example

Input:
2

Output:
3

Input:
3

Output:
4

Explanation

In the first sample, the words can be made are: "oo", "ox", "xo".

In the second sample, the words can be made are: "ooo", "oox", "oxo", "xoo"