입자

미르코는 유럽 입자물리 연구소(CERN)에 물리학자로 취직해서, 첫 과제로 최신 입자 가속기의 설계도를 그리는 일을 맡았다.

가속기에는 방이 정확히 $N$개 있고, 실험을 시작하는 순간 각 방에는 입자가 하나씩 놓여 있다. 방마다 그 뒤에 이어지는 방이 정확히 하나씩 정해져 있다. 1초가 지날 때마다 모든 입자는 지금 있는 방에서 그 방에 이어지는 방으로 동시에 옮겨간다. 방 $A$에 방 $B$가 이어져 있어도 방 $B$에 방 $A$가 이어져 있어야 하는 것은 아니다. 물론 두 방이 서로 이어져 있어도 된다.

실험에서 가장 중요한 조건은 $K$초가 지난 뒤 모든 입자가 처음 있던 방에 돌아와 있어야 한다는 것이다. 미르코는 이 조건을 만족하는 설계도를 몇 가지나 그릴 수 있는지 알고 싶다. 어떤 방에 이어지는 방이 서로 다르면 두 설계도는 서로 다른 설계도다. 설계도의 수가 매우 많을 수 있으므로 그 수를 $M$으로 나눈 나머지만 구한다.

참고로 방은 자기 자신에 이어질 수도 있다.

첫째 줄에 두 수 $N$과 $K$가 공백으로 구분되어 주어진다. ($1 \le K \le N \le 30000$) $N$은 미르코가 가속기를 만드는 데 쓸 수 있는 방의 총 개수이고, $K$는 모든 입자가 처음 있던 방으로 돌아와야 하는 시각(초)이다.

둘째 줄에 나머지를 구할 수 $M$이 주어진다. ($1 \le M \le 10^9$)

첫째 줄에 조건을 만족하는 서로 다른 설계도의 개수를 $M$으로 나눈 나머지를 출력한다.