409582: GYM103637 J Jenga

Jenga — board game invented in the distant 1970th year. In this game, bars are used, where the length of each bar is exactly three times its width, and the height is approximately equal to half its width. A tower is built from these bars, where each floor consists of three bars, and the bars of the next floor are laid perpendicular to the bars of the previous floor. Then the two players take out one bar from the turret one by one and place it on the upper floor perpendicular to the bars of the upper floor. At some point, the tower ceases to be stable and collapses under the influence of its own gravity. The player after the move which the tower collapses loses. The figure below shows an example of a tower after a certain number of moves.

  

A stable tower is considered to be a tower in which all floors except the upper one contain either at least two bars or one bar located in the middle of the floor. You are asked to calculate how many stable towers there are, consisting of exactly $$$n$$$ bars. Two towers are considered different if there is no such rotation about an axis perpendicular to the surface of the base combining these towers.

The only line contains a single integer $$$n$$$ — the number of Jenga bars.

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

Print a single integer — the number of possible ways to get a stable Jenga tower. Since the answer may be too large, it must be printed modulo $$$10^9+7$$$.

1

1

42

729888649

2

4