Summation of Binomial Coefficients with Step

Given four integers n, p, k, and r, define N = n \times k. We are interested in computing the following sum modulo p:

$$S = \left(\sum_{i \ge 0} C_{N}^{ik + r}\right) \bmod p, $$

where the binomial coefficient \( C_N^m \) is defined as

$$C_N^m = \frac{N!}{m!(N-m)!}, \quad 0 \le m \le N, $$

with the convention that \(0! = 1\) and \(C_N^m = 0\) when \(m > N\). In other words, the summation is taken over all nonnegative integers \(i\) such that \(ik+r \le N\).

You are to calculate the value of \(S\) modulo \(p\).

Example: For \(n=3,\, p=100,\, k=2,\, r=1\), we have \(N=6\) and the sum becomes:

$$S = C_6^1 + C_6^3 + C_6^5 = 6 + 20 + 6 = 32 \; (\bmod\, 100). $$

inputFormat

The input consists of a single line containing four space-separated integers n p k r as described above.

You can assume that \(0 \le n \le 50\) and that the other parameters are such that the computation can be performed using standard dynamic programming.

outputFormat

Output a single integer: the value of \(S = \left(\sum_{i\ge0} C_{nk}^{ik+r}\right) \bmod p\).

sample

3 100 2 1

32