#### 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 .

#### Constraints

#### Input Specification

A single integer, .

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

. Therefore, of the strings are valid.

## Comments