テスター募集中！
問題
あなたは「令」と「和」という文字をそれぞれ $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