시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB811100.000%

문제

Какая же операционная система без встроенных игр?

Вася уже почти написал игру и ему осталось лишь решить небольшую подзадачу --- необходимо посчитать число возможных состояний в конце игры.

В процессе игры $N$ одинаковых шаров раскладываются по $M$ одинаковым ящикам. Причем, в каждом ящике не может оказаться более $K$ шаров. Шары при этом никак не различаются, как и ящики. Таким образом, два случая, когда в первом ящике один шар, во втором --- два и, когда в первом два шара, а во втором --- один, не различаются.

Так как это число может быть очень большим, достаточно найти ответ по модулю $R$.

입력

Во входном файле задано четыре числа $N$ --- количество шаров, $M$ --- количество ящиков, $K$ --- максимальное количество шаров в каждом ящике ($0 \le N, M, K \le 1000$) и $R$ ($2 \le R \le 10^9$).

출력

В выходной файл выведите ответ на задачу --- остаток от деления числа различных размещений шаров на $R$.

예제 입력 1

2 2 2 1000

예제 출력 1

2

예제 입력 2

4 3 2 1000

예제 출력 2

2