406183: GYM102302 H Log Concave Sequences

Memory Limit:64 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

H. Log Concave Sequencestime limit per test2 secondsmemory limit per test64 megabytesinputstandard inputoutputstandard 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.

ExampleInput
3
Output
20

Source/Category

加入题单

上一题 下一题 算法标签: