← 返回题目列表

Codeforces · 830/D

D. 歌手之家

中文机器翻译题面 查看原题

众所周知,辛格之家的通道错综复杂、相互交织。让我们将 Singer k-house 定义为通过以下过程构建的图:获取高度为 k 的完整二叉树,并将每个顶点的边添加到其所有后继节点(如果它们尚不存在)。

歌手 4 号屋

计算 Singer k-house 中不经过同一顶点两次的非空路径的数量。如果访问顶点的集合或顺序不同,则两条路径是不同的。由于答案可能很大,因此输出它对 109 + 7 求模。

输入

唯一一行包含单个整数 k (1 ≤ k ≤ 400)。

输出

打印单个整数 — 任务模 109 + 7 的答案。

示例

输入 #1

2

输出 #1

9

输入 #2

3

输出 #2

245

输入 #3

20

输出 #3

550384565

注意

第一个示例中有 9 条路径(下图中顶点编号):1, 2, 3, 1-2, 2-1, 1-3, 3-1, 2-1-3, 3-1-2。

歌手 2 室