DT-Tiling

使用多米诺骨牌和三格骨牌，将一个 $2\times N$ 的矩形网格完全铺满。

多米诺骨牌由两个单位正方形沿公共边连接而成。以下两种三格骨牌都可以使用。

• 三个单位正方形排成一行的直条形骨牌。
• 从 $2\times2$ 正方形中去掉一格得到的 L 形骨牌。

可以旋转骨牌，使其与网格对齐。每种骨牌的数量均无限。骨牌之间不能重叠，也不能超出网格边界。

求铺法数量对 $1\,000\,000\,007$ 取模的结果。如果各块骨牌所占格子集合的集合不同，则视为不同的铺法。形状相同的骨牌之间不作区分。

输入格式如下：

$N$

输出铺法数量对 $1\,000\,000\,007$ 取模的结果。

• $1\leq N\leq10^{18}$.
• $N$ 是整数。