티칼

마야 인디언들이 티칼에 아름다운 신전을 지었다. 신전은 정 $n$각형이며 모든 변은 서로 구별되지 않는다. 전통에 따라 신전 안에 같은 모양의 우상 피규어 $k$개를 들여놓았다. 샤먼들은 피규어가 신전의 벽, 즉 $n$각형의 변 옆에 서 있어야 한다고 주장한다. 벽마다 서 있는 피규어의 개수는 달라도 된다. 인디언의 관습에 따라 대사제는 매일 아침 피규어를 새로운 배치로 옮겨 놓아야 한다.

신전이 완성된 뒤 영혼들이 인디언 앞에 나타나 말했다. 피규어의 배치가 한 번이라도 다시 나타나면 하늘이 땅에 떨어지고 바다가 넘쳐 세상이 끝난다. 영혼들은 또한 신전을 돌려서 얻은 배치는 같은 배치로 본다고 덧붙였다.

대사제는 피규어를 놓을 수 있는 서로 다른 배치가 몇 가지인지 알고 싶어 한다. 이 수가 매우 클 수 있으므로 소수 $p$로 나눈 나머지를 구한다.

첫 줄에 세 정수 $n$, $k$, $p$가 주어진다 ($3 \le n \le 500\,000$; $1 \le k \le 500\,000$; $10^6 < p < 10^9$). $p$는 소수임이 보장된다.

벽이 $n$개인 신전에 $k$개의 피규어를 놓는 서로 다른 배치의 수를 회전을 고려하여 구하고, 그 값을 $p$로 나눈 나머지를 한 정수로 출력한다.

두 번째 테스트 케이스에서 가능한 배치는 다음과 같다.

($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$)