Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

combinatorics

dp

trees

*2700

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Uniformly Branched Trees

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputA 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 (*p*_{u}, *p*_{v}) 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* and *mod* (1 ≤ *n* ≤ 1000, 2 ≤ *d* ≤ 10, 10^{8} ≤ *mod* ≤ 10^{9}) — 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

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/05/2023 10:45:30 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|