DT-Tiling

ドミノとトロミノを使って、$2\times N$ の長方形のマス目を隙間なく敷き詰める。

ドミノは、単位正方形を二つ、辺でつないだ形である。トロミノは次の両方の種類を使える。

• 単位正方形を三つ一直線につないだ形。
• $2\times2$ の正方形から一マスを取り除いた L 字形。

タイルはマス目に合わせて回転でき、各種類を何枚でも使える。タイル同士を重ねたり、マス目の外にはみ出させたりしてはならない。

敷き詰め方の数を $1\,000\,000\,007$ で割った余りを求めよ。各タイルが占めるマスの集合の集まりが異なる場合、異なる敷き詰め方とする。同じ形のタイル同士は区別しない。

入力は次の形式で与えられる。

$N$

敷き詰め方の数を $1\,000\,000\,007$ で割った余りを出力せよ。

• $1\leq N\leq10^{18}$.
• $N$ は整数である。