29549번 - Тикал 다국어

문제

В городе Тикал индейцы майя построили прекрасный храм. Храм представляет собой правильный $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$ --- простое.

출력

В выходной файл выведите единственное целое число --- число различных расстановок $k$ идолов в храме c $n$ стенами с точностью до поворота по модулю $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ドル$)