众所周知,辛格之家的通道错综复杂、相互交织。让我们将 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 室