Tikal

The Maya built a beautiful temple in the city of Tikal. The temple is a regular $n$-gon whose sides are indistinguishable. By tradition, $k$ identical idol figurines were placed inside the temple. The shamans insist that the figurines must stand by the walls of the temple, meaning the sides of the $n$-gon. Different walls may hold different numbers of figurines. Following custom, the Chief Shaman must rearrange the figurines into a new configuration every morning.

After the temple was built, spirits appeared and warned that once a configuration of figurines repeats, the sky will fall, the seas will overflow, and the world will end. They also clarified that configurations obtained by rotating the temple are considered the same.

The Chief Shaman asks how many distinct configurations of the figurines exist in the temple. Since this number can be very large, he wants the answer modulo the prime $p$.

The first line contains three integers $n$, $k$, and $p$ ($3 \le n \le 500\,000$; $1 \le k \le 500\,000$; $10^6 < p < 10^9$). It is guaranteed that $p$ is prime.

Print a single integer: the number of distinct arrangements of $k$ idols among the $n$ walls of the temple, counting configurations equal under rotation as one, modulo $p$.

In the second test case, the possible arrangements are:

($3$,$0$,$0$,$0$,$0$,$0$) ($2$,$1$,$0$,$0$,$0$,$0$) ($2$,$0$,$1$,$0$,$0$,$0$) ($2$,$0$,$0$,$1$,$0$,$0$) ($2$,$0$,$0$,$0$,$1$,$0$)

($2$,$0$,$0$,$0$,$0$,$1$) ($1$,$1$,$1$,$0$,$0$,$0$) ($1$,$1$,$0$,$1$,$0$,$0$) ($1$,$1$,$0$,$0$,$1$,$0$) ($1$,$0$,$1$,$0$,$1$,$0$)