1262 - 令和

テスター募集中！

問題

あなたは「令」と「和」という文字をそれぞれ $N$ 個持っています。
この $2$ 字を使って長さ $N$ の文字列を作ります。
このような文字列は $2^N$ 通り考えられます。
では「和」の文字が連続することのない文字列は何通りあるでしょうか？
例えば、 $N = 2$の時は 「令令」「令和」「和令」「和和」の $4$ 通りで、条件を満たすのは $3$ 通りです。
$N$ がそれ以外の場合は何通り考えられるか求めてください。
ただし値は非常に大きくなる可能性があるので $10^9+7$ で割ったあまりを出力してください。

入力

N

出力

ans

最後の改行を忘れずに。

制約

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

テストケース

例1

入力

1

出力

2

「令」「和」の $2$ 通りです。

例2

入力

10

出力

144