Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

combinatorics

dp

graphs

trees

*2800

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Singer House

time limit per test

2 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputIt 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.

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 10^{9} + 7.

Input

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

Output

Print single integer — the answer for the task modulo 10^{9} + 7.

Examples

Input

2

Output

9

Input

3

Output

245

Input

20

Output

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.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/27/2024 18:17:35 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|