Your task is to calculate the number of bit strings of length n.

For example, if n=3, the correct answer is 888, because the possible bit strings are 000, 001, 010, 011, 100, 101, 110, and 111.

Input

The only input line has an integer n.

Output

Print the result modulo 10^9 + 7.

Constraints

1 <= n <= 10^6

Example

Input:

Output:

In this problem, we need to count the bit strings having a length of n and Let's say n is 3, the possible bit strings are 000, 001, 010, 011, 100, 101, 110, and 111.

Let's understand what is expected in this problem, we need to just count the possible strings which are possible using the length n.

for the place we have the string as 000, and we know that at any bit we can change the bit in two ways either it is 1 or 0.

So, to solve this problem, we just have to find the total number of ways to find the bit strings.

That is just 2^n where n represents the length of the given string.
Let's think of using binary exponentiation.

Let's code the solution up.

#include<bits/stdc++.h>
using namespace std;

#define MOD 1000000007


int Bexp(int a, int b){
    long long ret=1; 
    for (;b;a=a*a%MOD,b>>=1) if (b&1) ret=ret*a%MOD; return ret;
}

int main(){
     int n;
     cin >> n;
     cout << Bexp(2,n);
}

The second thing is to calculate the binary exponentiation.

Let's see what is binary exponentiation.

The term refers to the exponentiation of a raised to the power b and we know that a^b can be calculated using binary exponentiation which refers to the process of multiplying a, b times.

Let's understand the process of binary exponentiation.

#define MOD 100000009
int binaryExponentiation(int a, int b){
       long long ans = 1;
       while(a){
             ans = (ans*a)%MOD;
             b = (b*b)%MOD;
             b >>= 1;
       }
}

That's all for this blog and I shall see you in the next one.

Bit Strings

Input

Output

Constraints

Example