Number of bit-strings
Given an integer
n, you are asked to calculate the number of different bit-strings of length n. As the resulting number might be too big, the output should contain the number of bit-strings modulo (1000000007).Input
The input contains a single integer
n (1 ≤ n ≤ ).Output
The program should print the number of bit-strings of length
n modulo .Examples
Input | Output |
3 | 8 |
2 | 4 |
Explanation
- 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