The combination number $C_n^m$ represents the number of ways to choose $m$ items from $n$ distinct items. For example, choosing two items from the three items $(1, 2, 3)$ can be done in three ways: $(1, 2), (1, 3), (2, 3)$. According to the definition of combination numbers, we can provide the general formula for calculating $C_n^m$:
$$C_n^m = \frac{n!}{m!(n - m)!}$$
where $n! = 1 \times 2 \times \dots \times n$. (Specifically, when $n = 0$, $n! = 1$; when $m > n$, $C_n^m = 0$.)
Xiao Cong learned about the relationship between $C_i^j$ and multiples of $k$ during NOIP. Now he wants to go further and study more properties of combination numbers. Xiao Cong discovered that whether $C_i^j$ is a multiple of $k$ depends on whether $C_i^j \pmod k$ is equal to $0$. This fascinating property sparked Xiao Cong's interest in the modulo operation. Now Xiao Cong has chosen four integers $n, p, k, r$, and he wants to know the value of:
$$\left( \sum_{i=0}^{\infty} C_{nk}^{ik+r} \right) \pmod p$$
That is, the value of:
$$\left( C_{nk}^r + C_{nk}^{k+r} + C_{nk}^{2k+r} + \dots + C_{nk}^{(n-1)k+r} + C_{nk}^{nk+r} + \dots \right) \pmod p$$
Input
The first line contains four integers $n, p, k, r$. The meanings of all integers are as described in the problem statement.
Output
Output a single integer representing the answer.
Examples
Input 1
2 10007 2 0
Output 1
8
Note 1
$$C_4^0 + C_4^2 + C_4^4 + \dots = 1 + 6 + 1 = 8$$
Input 2
20 10007 20 0
Output 2
176
Subtasks
- For 30% of the test cases, $1 \le n, k \le 30$, $p$ is a prime number;
- For another 5% of the test cases, $p = 2$;
- For another 5% of the test cases, $k = 1$;
- For another 10% of the test cases, $k = 2$;
- For another 15% of the test cases, $1 \le n \le 10^3, 1 \le k \le 50$, $p$ is a prime number;
- For another 15% of the test cases, $1 \le n \times k \le 10^6$, $p$ is a prime number;
- For another 10% of the test cases, $1 \le n \le 10^9, 1 \le k \le 50$, $p$ is a prime number;
- For 100% of the test cases, $1 \le n \le 10^9, 0 \le r < k \le 50, 2 \le p \le 2^{30} - 1$.