Игра с шариками

면접 대비

시간 제한2초메모리 제한1024 MB

요약

N개의 같은 공을 M개의 같은 상자에 넣되 상자마다 K개 이하가 되도록 하는 경우의 수를 R로 나눈 나머지를 구한다.

난이도: 보통10점 중 5점
유형: 동적 계획법, 조합론, 수학, 구현
정답자: 아직 제출이 없습니다

문제

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

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

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

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

입력

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

출력

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

예제2

예제 1
입력
```
2 2 2 1000
```
예상 출력
```
2
```
예제 2
입력
```
4 3 2 1000
```
예상 출력
```
2
```