問題文

正の整数 N が与えられるので、4^0 + 4^1 + \dots + 4^N を 1\,000\,000\,007 で割った余りを出力してください。

制約

• 1 \leq N \leq 10^{18}
• N は整数

入力例 1

3

出力例 1

85

4^0 + 4^1 + 4^2 + 4^3 = 1 + 4 + 16 + 64 = 85 なので、85 を出力します。

入力例 2

45

出力例 2

414031736

4^0 + 4^1 + \dots + 4^{45} = 1650586719047173699865498965 なので、1650586719047173699865498965 を 1\,000\,000\,007 で割った余り 414031736 を出力します。