English · Original
Chinese · Translation
Formal · Original
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.
<center> Singer 4\-house</center>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.
## Input
The only line contains single integer _k_ (1 ≤ _k_ ≤ 400).
## Output
Print single integer — the answer for the task modulo 109 + 7.
[samples]
## 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_.
<center> Singer 2\-house</center>
[{"iden":"statement","content":"已知 Singer 房屋中的通道复杂且交错。定义一个 Singer #cf_span[k]-房屋为通过以下过程构建的图：取一个高度为 #cf_span[k] 的完全二叉树，并为每个顶点添加指向其所有后继顶点的边（若这些边尚未存在）。\n\n计算 Singer #cf_span[k]-房屋中不经过同一顶点两次的非空路径的数量。若两条路径访问的顶点集合或顺序不同，则认为它们是不同的。由于答案可能很大，请输出其对 #cf_span[109 + 7] 取模的结果。\n\n输入仅包含一个整数 #cf_span[k]（#cf_span[1 ≤ k ≤ 400]）。\n\n请输出一个整数 —— 本题答案对 #cf_span[109 + 7] 取模的结果。\n\n在第一个例子中，共有 #cf_span[9] 条路径（顶点编号如下图所示）：_1_, _2_, _3_, _1-2_, _2-1_, _1-3_, _3-1_, _2-1-3_, _3-1-2_。"}, {"iden":"input","content":"输入仅包含一个整数 #cf_span[k]（#cf_span[1 ≤ k ≤ 400]）。"},{"iden":"output","content":"请输出一个整数 —— 本题答案对 #cf_span[109 + 7] 取模的结果。"},{"iden":"examples","content":"输入2输出9输入3输出245输入20输出550384565"},{"iden":"note","content":"在第一个例子中，共有 #cf_span[9] 条路径（顶点编号如下图所示）：_1_, _2_, _3_, _1-2_, _2-1_, _1-3_, _3-1_, _2-1-3_, _3-1-2_。 #cf_span(class=[tex-font-size-small], body=[Singer #cf_span[2]-house]) "}]
注意：根据要求，所有数学公式（如 #cf_span[k]、#cf_span[109 + 7]）和 Typst 命令（如 _1_、#cf_span(...)）均原样保留，未作任何改动或转义。自然语言部分已准确翻译为中文，术语统一为“交错和”、“测试用例”、“序列”等，结构与原内容完全一致。
**Definitions**
Let $ k \in \mathbb{Z} $ with $ 1 \leq k \leq 400 $.
Let $ T_k $ be the complete binary tree of height $ k $, with vertex set $ V_k $ and parent-child edges.
Let $ G_k = (V_k, E_k) $ be the **Singer $ k $-house**, defined as the graph obtained by taking $ T_k $ and adding all edges from each vertex to all its descendants (if not already present). Thus, $ E_k $ contains:
- All parent-child edges of $ T_k $,
- All direct edges from each vertex to every strict descendant (i.e., $ G_k $ is the transitive closure of $ T_k $ as a directed graph, but interpreted as an undirected graph with bidirectional edges).
**Constraints**
- $ |V_k| = 2^{k+1} - 1 $ (number of vertices in a complete binary tree of height $ k $).
- $ G_k $ is an undirected graph where for any two vertices $ u, v $, if $ u $ is an ancestor of $ v $ in $ T_k $, then $ \{u, v\} \in E_k $.
**Objective**
Count the number of **non-empty simple paths** in $ G_k $ (i.e., paths with no repeated vertices), where two paths are distinct if their sequences of vertices differ (order matters).
Let $ P_k $ denote this count.
Compute $ P_k \mod (10^9 + 7) $.
API Response (JSON)
{
"problem": {
"name": "D. Singer House",
"description": {
"content": "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",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 524288
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF830D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "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...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "[{\"iden\":\"statement\",\"content\":\"已知 Singer 房屋中的通道复杂且交错。定义一个 Singer #cf_span[k]-房屋为通过以下过程构建的图：取一个高度为 #cf_span[k] 的完全二叉树，并为每个顶点添加指向其所有后继顶点的边（若这些边尚未存在）。\\n\\n计算 Singer #cf_span[k]-房屋中不经过同一顶点两次的非空路径的数量。若两条路径...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ k \\in \\mathbb{Z} $ with $ 1 \\leq k \\leq 400 $. \nLet $ T_k $ be the complete binary tree of height $ k $, with vertex set $ V_k $ and parent-child edges. \nLet $ G_k = (V_k, E_...",
"is_translate": false,
"language": "Formal"
}
]
}