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

#F1057. Uniformly Branched Trees

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

Uniformly Branched Trees

题目描述

F. Uniformly Branched Trees
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A tree is a connected graph without cycles.

Two trees, consisting of n vertices each, are called isomorphic if there exists a permutation p:{1,...,n}→{1,...,n} such that the edge (u,v) is present in the first tree if and only if the edge (pu,pv) is present in the second tree.

Vertex of the tree is called internal if its degree is greater than or equal to two.

Count the number of different non-isomorphic trees, consisting of n vertices, such that the degree of each internal vertex is exactly d. Print the answer over the given prime modulo mod.

Input

The single line of the input contains three integers n, d andmod (1≤n≤1000, 2≤d≤10, 108≤mod≤109) − the number of vertices in the tree, the degree of internal vertices and the prime modulo.

Output

Print the number of trees over the modulo mod.

Examples
Input
5 2 433416647
Output
1
Input
10 3 409693891
Output
2
Input
65 4 177545087
Output
910726


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