406183: GYM102302 H Log Concave Sequences

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

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 10⁹ + 7.

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

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

3

20