Description

This reminds Ran (然) of the time spent with Yu (雨). Since Yu is a girl who loves to play, they have many toys. Among them there is a kind of toy that looks like a white dragonfly, and it is now kept by Ran, with a total of $n$ of them. The wing lengths of the white dragonflies are $1,2,\dots,n$ respectively, and each pair of wings can be opened to any angle in $(0,\pi)$. Ran thinks that choosing $m$ of these white dragonflies and opening their wings so that the distance between the tips of the two wings is an integer, and all these distances are pairwise distinct, is like weaving a memory. He considers two memories the same if and only if the $m$ white dragonflies can be reordered in some way and matched one-to-one such that the corresponding dragonflies have the same wing length and the same distance between wing tips. He wants you to tell him how many different memories can be woven. You only need to output $ans \bmod{p}$.

Input Format

One line with three positive integers $n,m,p$.

Output Format

One line with one integer, representing the answer.

32 2 47

36

233 223 1926817

620162

3 1 7

2

Hint

Brief statement of the problem

Count the number of different groups consisting of $m$ isosceles triangles, where the equal side length $a$ satisfies $1 \le a \le n$, the base length $b$ satisfies $1 \le b \le 2a-1$, and both are integers; all side lengths $a$ are pairwise distinct, and all base lengths $b$ are also pairwise distinct. Two groups are the same if and only if the $m$ triangles can be reordered in some way and matched one-to-one so that the corresponding triangles are congruent.

Sample explanation

Due to space limits, only Sample $3$ is explained.

One can weave $1,1,1$, $2,2,1$, $2,2,2$, $2,2,3$, $3,3,1$, $3,3,2$, $3,3,3$, $3,3,4$, $3,3,5$, for a total of $9$ kinds of memories, and after taking modulo $7$ the result is $2$.

This problem uses bundled tests. The score and constraints of each subtask are as follows.

For all testdata, $1 \le m \le n \le 10^{18},1 \le p \le 10^5$, and $p$ is not guaranteed to be prime.

Translated by ChatGPT 5