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>
已知辛格之家的通道复杂且交错。定义一个辛格 #cf_span[k]-家为通过以下过程构建的图：取一个高度为 #cf_span[k] 的完全二叉树，并为每个顶点添加指向其所有后继顶点的边（如果这些边尚未存在）。
计算辛格 #cf_span[k]-家中不经过同一顶点两次的非空路径的数量。若两个路径访问的顶点集合或顺序不同，则视为不同路径。由于答案可能很大，请输出其对 #cf_span[109 + 7] 取模的结果。
仅一行包含一个整数 #cf_span[k]（#cf_span[1 ≤ k ≤ 400]）。
输出一个整数——该任务的答案对 #cf_span[109 + 7] 取模的结果。
在第一个例子中存在 #cf_span[9] 条路径（顶点编号如下图所示）：_1_, _2_, _3_, _1-2_, _2-1_, _1-3_, _3-1_, _2-1-3_, _3-1-2_。
## Input
仅一行包含一个整数 #cf_span[k]（#cf_span[1 ≤ k ≤ 400]）。
## Output
输出一个整数——该任务的答案对 #cf_span[109 + 7] 取模的结果。
[samples]
## Note
在第一个例子中存在 #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=[辛格 #cf_span[2]-家])
**Definitions**
Let $ k \in \mathbb{Z} $, $ 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 graph, where $ E_k $ contains:
- All edges of $ T_k $,
- Additional edges from each vertex to all its descendants (not already present), making $ G_k $ a DAG where every vertex has directed edges to all vertices in its subtree.
**Constraints**
- $ |V_k| = 2^{k+1} - 1 $
- $ G_k $ is a directed acyclic graph with edges from each node to all its descendants (including indirect ones).
- Paths are directed, simple (no repeated vertices), and non-empty.
**Objective**
Compute the number of non-empty simple directed paths in $ G_k $, modulo $ 10^9 + 7 $.
That is, count all sequences $ (v_1, v_2, \dots, v_m) $, $ m \geq 1 $, such that:
- $ v_i \in V_k $,
- $ v_i \neq v_j $ for $ i \neq j $,
- For each $ i \in \{1, \dots, m-1\} $, there is a directed edge from $ v_i $ to $ v_{i+1} $ in $ G_k $ (i.e., $ v_{i+1} $ is a descendant of $ v_i $).
Let $ P(k) $ denote this count.
Output $ P(k) \mod (10^9 + 7) $.
API Response (JSON)
{
"problem": {
"name": "E. 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": "CF823E"
},
"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": "已知辛格之家的通道复杂且交错。定义一个辛格 #cf_span[k]-家为通过以下过程构建的图：取一个高度为 #cf_span[k] 的完全二叉树，并为每个顶点添加指向其所有后继顶点的边（如果这些边尚未存在）。\n\n计算辛格 #cf_span[k]-家中不经过同一顶点两次的非空路径的数量。若两个路径访问的顶点集合或顺序不同，则视为不同路径。由于答案可能很大，请输出其对 #cf_span[109 + 7...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ k \\in \\mathbb{Z} $, $ 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_k) $...",
"is_translate": false,
"language": "Formal"
}
]
}