← 返回题目列表

Codeforces · 724/F

F. 均匀分枝的树

中文机器翻译题面 查看原题

树是没有循环的连通图。

如果存在排列 p: {1, ..., n} → {1, ..., n} 使得边 (u, v) 出现在第一棵树中当且仅当边 (pu, pv) 出现在第二棵树中,则两棵树(每棵树由 n 个顶点组成)被称为同构。

如果树的度数大于或等于 2,则该树的顶点称为内部顶点。

计算由 n 个顶点组成的不同非同构树的数量,使得每个内部顶点的度恰好为 d。打印给定素数模模的答案。

输入

输入的单行包含三个整数 n、d 和 mod (1 ≤ n ≤ 1000, 2 ≤ d ≤ 10, 108 ≤ mod ≤ 109) — 树中的顶点数、内部顶点的度数和素数模。

输出

打印模 mod 上的树数。

示例

输入 #1

5 2 433416647

输出 #1

1

输入 #2

10 3 409693891

输出 #2

2

输入 #3

65 4 177545087

输出 #3

910726