Problem Description

The combination number \( C_n^m \) represents the number of ways to choose \( m \) items from \( n \) distinct items. For example, from the three items \((1, 2, 3)\), choosing two items can be done in three ways: \((1, 2)\), \((1, 3)\), and \((2, 3)\). According to the definition of the combination number, 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 \cdots \times n \). (Specifically, when \( n = 0 \), \( n! = 1 \); when \( m > n \), \( C_n^m = 0 \).)

During the NOIP competition, Xiao Cong learned about the relationship between \( C_i^j \) and multiples of \( k \). Now, he wants to delve deeper into the properties of combination numbers. Xiao Cong found that whether \( C_i^j \) is a multiple of \( k \) depends on whether \( C_i^j \bmod k \) equals 0, a fascinating property that piqued his interest in the modulo operation (remainder 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) \bmod p, \]

which is equivalent to

\[ \left( C_{nk}^{r} + C_{nk}^{k + r} + C_{nk}^{2k + r} + \cdots + C_{nk}^{(n - 1)k + r} + C_{nk}^{nk + r} + \cdots \right) \bmod p. \]

Input Format

The first line contains four integers \( n, p, k, r \), with the meanings as described in the problem statement.

Output Format

Output a single integer representing the answer.

Sample Input and Output

Sample Input #1

2 10007 2 0

Sample Output #1

8

Sample Input #2

20 10007 20 0

Sample Output #2

176

Notes/Hints

For 30% of the test cases, \( 1 \leq n, k \leq 30 \), and \( 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 \leq n \leq 10^3, 1 \leq k \leq 50 \), and \( p \) is a prime number;
For another 15% of the test cases, \( 1 \leq n \times k \leq 10^6 \), and \( p \) is a prime number;
For another 10% of the test cases, \( 1 \leq n \leq 10^9, 1 \leq k \leq 50 \), and \( p \) is a prime number;
For 100% of the test cases, \( 1 \leq n \leq 10^9, 0 \leq r < k \leq 50, 2 \leq p \leq 2^{30} - 1 \).

见题面 Input 部分

见题面 Output 部分