## A Euclid Problem

View as PDF

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 .

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

#### Input Specification

A single integer, .

#### 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 possible strings of length , one of them contains the consecutive letters ABBA. Therefore, of the strings are valid.

#### Sample Explanation 2

Official Explanation (Page 11-12)