CF830D.Singer House

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.

众所周知，Singer 房屋中的通道结构复杂且相互交织。我们定义 Singer k-house 为通过以下过程构造的图：取一棵高度为 k 的完全二叉树，并对每个顶点，若其所有后继顶点之间尚无边相连，则添加一条边连接该顶点与其所有后继顶点。

Singer 4-house

请计算 Singer k-house 中不重复经过同一顶点的非空路径数目。若两条路径所访问顶点的集合不同，或顶点访问顺序不同，则视为不同的路径。由于答案可能很大，请输出其对 $10^9 + 7$ 取模的结果。

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

唯一的一行包含一个整数 $k$（$1 \leq k \leq 400$）。

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

输出一个整数——该任务答案对 $10^9 + 7$ 取模的结果。

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

第一个示例中有 9 条路径（顶点编号见下方图示）：1、2、3、1-2、2-1、1-3、3-1、2-1-3、3-1-2。

Singer 2-house