1.1 The Magician

Score: 10pts

Time Limit: 2.00 sec

Imagine you're a bit string magician, tasked with generating bit strings of length n. Let's say n=3 – your goal is to conjure up a variety of these sequences. Think of it as creating a captivating story using only two characters: 0 and 1. For instance, with n=3, you'd be weaving tales like 000, 001, 010, 011, 100, 101, 110, and 111. Your challenge is to calculate the number of these intriguing narratives you can craft!

Constraints

1 ≤ n ≤ 10^6

Time limit : 1.00s

Memory limit : 512MB

Time limit : 1.00s

Memory limit : 512MB

Input Format

The only input line has an integer n.

Output Format

Print the result modulo

10^9+7

10^9+7

Example 1

Input:

3

Output:

8

Explanation:

Explanation is given in problem statement

3

Output:

8

Explanation:

Explanation is given in problem statement