#P830D. Singer House

    ID: 3942 Type: RemoteJudge 2000ms 512MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>combinatoricsdpgraphstrees*2800

Singer House

No submission language available for this problem.

Description

It is known that passages in Singer house are complex and intertwined. Let's define a Singer k-house as a graph built by the following process: take complete binary tree of height k and add edges from each vertex to all its successors, if they are not yet present.

Singer 4-house

Count the number of non-empty paths in Singer k-house which do not pass the same vertex twice. Two paths are distinct if the sets or the orders of visited vertices are different. Since the answer can be large, output it modulo 109 + 7.

The only line contains single integer k (1 ≤ k ≤ 400).

Print single integer — the answer for the task modulo 109 + 7.

Input

The only line contains single integer k (1 ≤ k ≤ 400).

Output

Print single integer — the answer for the task modulo 109 + 7.

Samples

2

9

3

245

20

550384565

Note

There are 9 paths in the first example (the vertices are numbered on the picture below): 1, 2, 3, 1-2, 2-1, 1-3, 3-1, 2-1-3, 3-1-2.

Singer 2-house