Problem Description

You have probably seen the scene where many people hold hands and dance around a bonfire. In general, when everyone dances hand in hand, they form one big circle: each person's left hand holds the right hand of the friend next to them, and their right hand holds the left hand of the friend on the other side.

However, if everyone randomly holds the hands of two different people and then slowly spreads out, things become much more interesting. At this time, everyone will still form circles, but they may form several independent circles. Of course, we still require that a person's right hand can only hold another person's left hand, and vice versa.

There are $N$ students in the class, numbered from $1$ to $N$. Will wants to know how many essentially different hand-holding arrangements will make them form exactly $k$ circles after they spread out.

Given two arrangements, if there exists a person and one of their hands such that, in these two arrangements, the number of the person holding that hand is different, then these two arrangements are essentially different.

Input Format

One line containing three positive integers $N,~k,~P$.

Output Format

Output one integer in one line, representing the remainder of the number of essentially different arrangements modulo $p$. It is guaranteed that $p$ is a prime number.

3 1 1000000009 

2

Hint

Constraints:

$3~\leq~3k~\leq~N~\leq~3000$.

$10^4~\leq~p~\leq~2~\times~10^9$.

Translated by ChatGPT 5