D. abbaaaba
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

How many words of length $$$n$$$ formed by 'a' and 'b' are there that do not contain the word 'abbaaaba'?

Write the result modulo $$$10^{9}+7$$$.

Input

An integer $$$n$$$.

Output

A line with the result.

Scoring

$$$1 \leq n \leq 10^{18}$$$

There are 100 cases and each case is worth one point.

Example
Input
8
Output
255