跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F0687. Singer House

  • ID: 693
  • 传统题
  • 2000ms
  • 256MiB
  • 尝试: 0
  • AC · 已通过: 0
  • 教学难度:挑战
  • 上传者:
  • 组合数学
  • 动态规划
  • 图论
  • 树
  • 数学
  • 数据结构
  • 挑战
  • 难度
  • 共享题库
  • Codeforces
  • 英文题面
  • 题目来源
  • 题面语言

Singer House

题目描述

D. Singer House
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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-house

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.

Examples
Input
2
Output
9
Input
3
Output
245
Input
20
Output
550384565
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.

Singer 2-house


题目来源:fps-www.educg.net-codeforce-1-2833.xml.zip;FPS 共享题包,题包内第 101 题。保留原作者与原赛事署名。