Pascal's Triangle

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.


Input Specification

The first line will contain one integer: n


Output Specification

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


Constraints

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


Sample input 1

1


Ouput for sample input 1

2


Explanation for sample case 1

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

Comments
  • There are no comments.