Background

Problem 9A on the 2016 Euclid was stated as follows:

The string AAABBBAABB is a string of ten letters, each of which is A or B, that does not include the consecutive letters ABBA.

The string AAABBAAABB is a string of ten letters, each of which is A or B, that does include the consecutive letters ABBA.

Determine, with justification, the total number of strings of ten letters, each of which is A or B, that do not include the consecutive letters ABBA.

Problem Statement

Since computers are pretty fast, we've decided to replace ten with ~N~.

Determine, without justification, the total number of strings of ~N~ letters, each of which is A or B, that do not include the consecutive letters ABBA, modulo ~1~ ~000~ ~000~ ~007~.

Constraints

~N \leq 10^{18}~

Input Specification

A single integer, ~N~.

Output Specification

A single integer, the answer.

Sample Input 1

4

Sample Output 1

15

Sample Input 2

10

Sample Output 2

631

Sample Input 3

123123123

Sample Output 3

952227253

Sample Explanation 1

Out of the ~2^4~ possible strings of length ~4~, one of them contains the consecutive letters ABBA. Therefore, ~15~ of the strings are valid.

Sample Explanation 2

Official Explanation (Page 11-12)