说明

本题不再提供附加样例文件。

题目描述

Farmer John 要把他的 N 头公牛和 M 头母牛排成一排，并且希望任意的一个区间内公牛与母牛的数量之差的绝对值不超过 K。

问：John 有多少种不同的排队方案？答案可能很大，你需要将其 mod P 后输出。

输入格式

一行，四个整数 N, M, K, P

输出格式

一个整数，表示答案。

样例1输入

1 2 1 123

样例1输出

2

样例2输入

996 987 18 998244353

样例2输出

425563495

数据范围

40分：N, M ≤ 200，K ≤ 20，0 < P < $2^{31}$（其中有 12 分：N, M ≤ 20）。

30分：N, M ≤ 1000，K ≤ 20，0 < P < $2^{31}$。

30分：N, M ≤ 1000，K ≤ 50，0 < P < $2^{31}$。