Dictionary

We wish to create a dictionary of artificial words. The words have to fulfill the following criteria:

• The words contain only letters a, b, and c.
• The length of each word is exactly n.
• A letter never appears on its own; it will always belong to a sequence of 2, 3, or 4 identical letters.
• Any two identical letters from different sequences are separated by at least 4 other letters.

Examples and counterexamples for length n = 12:

The following examples of length 12 are words: aaaabbbbaaaa, aaabbbccaaaa, aabbccaaaacc, aabbccaabbcc.

The following examples of length 12 are not words:

• aaabbbaaaabb: there are two letters a from different sequences that are not separated by at least 4 letters.
• aaaaabbcccaa: there is a sequence of letters a with a length greater than 4.
• aaaabbcccaab: there is a sequence consisting of a single letter b.

The dictionary must contain all words of a given length n.

For a given natural number n, calculate the number of words that will be written in the dictionary.

Input Specification

The input consists of a single line containing a single value of the natural number n (1 ≤ n ≤ 2⁶³).

Output Specification

Output a single line containing the number obtained as the remainder after dividing the number of words of length n by 1 000 000 007.

Sample Input 1

1. 6

download as text file

Output for Sample Input 1

1. 24

download as text file

Sample Input 2

1. 46

download as text file

Output for Sample Input 2

1. 317046901

download as text file

Sample Input 3

1. 20192019

download as text file

Output for Sample Input 3

1. 31255839

download as text file

Explanation

In Sample 1, we have the following 24 words:

aaaabb, aaaacc, aaabbb, aaaccc, aabbbb, aabbcc, aaccbb, aacccc, bbaaaa, bbaacc, bbbaaa, bbbbaa, bbbbcc, bbbccc, bbccaa, bbcccc, ccaaaa, ccaabb, ccbbaa, ccbbbb, cccaaa, cccbbb, ccccaa, ccccbb

In Sample 2, the number of words of length 46 is 1 317 046 908, and the remainder of the division by 1 000 000 007 is 317 046 901.