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:

```
3
```

Output:

```
8
```

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.