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

  1. 3: 000, 001, 010, 011, 100, 101, 110, 111
  1. 2: 00, 01, 10, 11
Β 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue