問題文

縦 $2$ 行、横 $N$ 列のグリッドがあり、それぞれのグリッドのマスを黒色または白色に塗りつぶします。 このとき、次の条件を満たすグリッドの塗り方は何通りありますか?

• 黒色に塗られたマスは、他の黒色に塗られたマスと辺で隣接していない

ただし、答えは非常に大きくなることがあるので、答えを $10^9+7$ で割った余りを求めてください。

Note: $500$ms以内で解きましょう

制約

• $1 \leq N \leq 2\times10^{15}$
• $N$は整数

入力

入力は以下の形式で標準入力から与えられる。

N 

出力

答えを一行に出力して、最後に改行せよ。

サンプル

1

3

2

7

7

577

3141592

899010756