시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 64 MB 0 0 0 0.000%

문제

Mirko se preko veze zaposlio kao fizičar u Europskoj Organizaciji za Nuklearna Istraživanja (CERN) te je kao prvi zadatak dobio izradu nacrta za najnoviji ubrzivač čestica. Ubrzivač će imati točno N komora u kojima se na početku svakog pokusa nalazi po jedna čestica. Na svaku komoru se nastavlja točno jedna komora. Svake sekunde se sve čestice prebace iz komore u kojoj se trenutno nalaze u komoru koja se nju nastavlja. Primijetite da ako se na komoru A nastavlja komora B, nije nužno da na komoru B nastavlja komora A, iako je i to moguće. Za pokuse je izuzetno važno je da nakon K sekundi sve čestice budu u svojim početnim komorama.

Mirka zanima na koliko načina može napraviti nacrt za ubrzivač sa traženim svojstvima. Dva nacrta se razlikuju ukoliko postoji komora na koju se u ta dva nacrta nastavljaju različite komore. Kako nacrta može biti jako mnogo, potrebno je odrediti samo ostatak pri dijeljenju broja nacrta sa modulom M.

Napomena: Komora se može nastavljati na samu sebe. 

입력

U prvom retku nalaze se brojevi N i K odvojeni razmakom, 1 ≤ K ≤ N ≤ 30 000. Broj N predstavlja ukupan broj komora koje Mirko ima na raspolaganju za gradnju ubrzivača, a K je broj sekundi nakon kojeg sve čestice moraju biti u svojim početnim komorama.

U drugom retku nalazi se broj M, 1 ≤ M ≤ 109 , modul. 

출력

U prvi i jedini redak izlaza potrebno je ispisati ostatak pri dijeljenju broja različitih nacrta s brojem M. 

예제 입력 1

2 1
1000

예제 출력 1

1

예제 입력 2

3 2
1000

예제 출력 2

4

예제 입력 3

4 4
6

예제 출력 3

4