P7488 "Stoi2031" Black Sweater

> Watching those white dragonflies, forgetting to move forward in the air. Can I re-weave the memories that have become fuzzy in my mind, and say "I love you" again? Maybe then the rain would not stop either. Where is the black sweater hidden? Let the memories stay there forever. —— "Black Sweater"

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}$.

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

One line with one integer, representing the answer.

#### 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.** | Subtask No. | $m \le n \le$ | Special Constraints | Score | | :-----------: | :-----------: | :-----------: | :-----------: | | $1$ | $10^3$ | None | $13$ | | $2$ | $10^6$ | None | $37$ | | $3$ | $10^{18}$ | None | $37$ | | $4$ | $10^{18}$ | $p$ is prime | $13$ | 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