No.621 Number of Ways to Place Dominoes on a 3 x N Grid
Problem Statement
A grid consisting of $3$ cells vertically and $N$ cells horizontally is called a $3 \times N$ grid.
The figure below shows a $3 \times 10$ grid.
Find the total number of "ways to place dominoes of size $1 \times 2$ on the cells of a $3 \times N$ grid, so that dominoes do not overlap each other and do not stick out of the grid, until no more dominoes can be placed", modulo $10^9 + 7$.
Dominoes may be rotated. Individual dominoes are not distinguished.
Note that the grid does not need to be completely filled with dominoes.
Input
$N$
$1 \le N \le 10^{18}$
$N$ is an integer.
Output
Output the answer in one line.
Print a newline at the end.
Sample
Sample 1
Input
2
Output
5
These are the $5$ ways.
Placements such as this one are not counted, because another domino can still be placed.
Sample 2
Input
20
Output
718700373
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
しらっ亭