Given an integer n, find the sum nC0 + nC1 + nC2 + ... + nCn where xCy is the number of ways that y items can be chosen from a list of x items. Since the answer can be very large, mod the answer by 1000000007.

The first line will contain one integer: n

On a single line, print one integer: the sum specified in the problem statement modded by 1000000007.

Subtask 1 (10 points): 1 ≤ n ≤ 8

Subtask 2 (10 points): 1 ≤ n ≤ 20

Subtask 3 (40 points): 1 ≤ n ≤ 10^5

Subtask 4 (40 points): 1 ≤ n ≤ 10^12

`1`

`2`

1C0 = 1, 1C1 = 1; 1C0 + 1C1 = 1 + 1 = 2

- Points: 7
- Time limit: 2.0s
- Memory limit: 64.0M
- Author: jimmyliu
- Category: Classics
- Type: Simple Math, Divide and Conquer
- All Submissions Best Submissions

Comments

- There are no comments.