ビット列の数
整数 n が与えられたとき、長さ n の異なる bit-strings（ビット列）の総数を求める問題です。結果の値が非常に大きくなる可能性があるため、出力はこのビット列の総数を （1000000007）で割った余りを返す必要があります。
入力
入力は単一の整数 n（1 ≤ n ≤ ）です。
出力
長さ n のビット列の総数を で割った余りを出力してください。
例
入力 | 出力 |
|---|---|
3 | 8 |
2 | 4 |
解説
3: 000, 001, 010, 011, 100, 101, 110, 111
2: 00, 01, 10, 11
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB