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