A Euclid Problem

View as PDF

Submit solution


Points: 15
Time limit: 1.0s
Memory limit: 128M

Problem type

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)


Comments

There are no comments at the moment.