Candy

Time limit2sMemory limit512 MB

Summary

Sum 2^K over all subsets of N candies with K elements, where the empty subset contributes 0, modulo 1,000,000,007.

Level: Medium4 of 10
Topics: Combinatorics, Math, Dynamic programming, Number theory
Solved: No attempts yet

Problem

Younghee prepared $N$ candies, each with a different flavor, packed them in a box, wrapped it, and planned to give it to Chulsoo. The candies are numbered 1 through $N$ by flavor.

On the birthday the wrapping was already torn open. Younghee had told Chulsoo that the box originally held $N$ candies, so Chulsoo suspects some of them are gone. None of them may be missing, or all of them may be missing. In other words, the candies Chulsoo actually received form an arbitrary subset of the candies numbered 1 through $N$ .

If Chulsoo receives $K$ candies with $1 \le K \le N$ , his satisfaction is $2^K$ . For example, if he receives candies 1, 3, and 4, that is 3 candies, so his satisfaction is $2^3 = 8$ . If he receives no candy at all, his satisfaction is 0.

Compute the sum of the satisfaction over every case Chulsoo could have received, that is over all $2^N$ subsets.

Input

The first line contains the number of distinct candies $N$ ( $2 \le N \le 100000$ ).

Output

Print the total satisfaction modulo 1,000,000,007 on the first line.

Hint

Take $N = 2$ . Receiving only candy 1 gives satisfaction 2, receiving only candy 2 gives 2, receiving both gives 4, and receiving nothing gives 0. The total is $2 + 2 + 4 = 8$ .

Examples3

Example 1
Input
```
2
```
Expected output
```
8
```
Example 2
Input
```
3
```
Expected output
```
26
```
Example 3
Input
```
5
```
Expected output
```
242
```