树是没有循环的连通图。
如果存在排列 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