Bit Strings

Task:

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

For example, if $n=3$, the correct answer is $8$, 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 \le n \le 10^6$
  

Solutions:

It's quite straightforward. The formula is $2^n$ where $n$ is input. The noticeable thing is moduling for $1e9+7$, and luckily function $pow$ can do it perfectly.

1def helper(n):
2    return pow(2,n,int(1e9+7))
3a=int(input())
4print(helper(a))
5 

Time complexity: $O(1)$

Space complexity: $O(1)$