H. Log Concave Sequences
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

A sequence of numbers A is said to be logarithm concave if, and only if, for every 2 ≤ i ≤ n - 1, ai - 1 * ai + 1 ≤ ai2.

For example the sequence A = (1, 2, 3) is logarithm concave. The sequence A = (2, 2, 3) is not logarithm concave.

In this problem, you will have to answer what is the number of log concave sequences which contain only the numbers 0, 1 or 2, with N elements.

As this number could be very large, print the answer mod 109 + 7.

Input

The input consists of a single integer N (3 ≤ N ≤ 1018) indicating the size of the log concave sequence.

Output

One integer with the number of log concave sequences with size N that contains only the numbers 0, 1 or 2.

Example
Input
3
Output
20