Singer House
题意翻译
一棵k-树由深度为k的满二叉树，每个节点均与其所有祖先（包括间接的）连边（如果这条边不存在的话）得到。
求k-树中每个节点最多经过一次的不同有向路径数量。
translated by @vanilla
题目描述
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 $ -houseCount 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 $ 10^{9}+7 $ .
输入输出格式
输入格式
The only line contains single integer $ k $ ( $ 1<=k<=400 $ ).
输出格式
Print single integer — the answer for the task modulo $ 10^{9}+7 $ .
输入输出样例
输入样例 #1
2
输出样例 #1
9
输入样例 #2
3
输出样例 #2
245
输入样例 #3
20
输出样例 #3
550384565
说明
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