Problem Description

For a sequence \( a \) of length \( n \), define \( f(a) = \dfrac{1}{\prod\limits_{i=k}^n s_i} \), where \( s_i \) is the prefix sum array of \( \{a_n\} \), and \( k \) is a given constant with \( 1 \le k \le 2 \).

Consider all sequences \( a \) that satisfy the following three conditions:

• \( a \) has length \( n \).
• \( \forall i, j \), \( a_i \ne a_j \).
• \( 1 \le a_i \le m \).

Find the sum of \( f(a) \) for all such sequences, and output the result modulo \( p \). It is guaranteed that \( p \) is a prime number.

Input Format

The first line contains four integers \( n, m, k, p \), representing the length of the sequence, the upper bound of the sequence elements, the constant \( k \), and the modulus, respectively.

Output Format

Output a single integer representing the result modulo \( p \).

Sample Input and Output

Input Sample #1

2 3 2 1000000007

Output Sample #1

966666675

Input Sample #2

3 5 2 998244353

Output Sample #2

148276980

Input Sample #3

6 10 2 1004535809

Output Sample #3

622165218

Input Sample #4

15 20 2 1064822107

Output Sample #4

53789887

Input Sample #5

30 40 1 265371653

Output Sample #5

179937201

Notes

For all data, it is guaranteed that \( 2 \le n \le m \le 100 \), \( 10^8 < p < 1.07 \times 10^9 \) and \( p \) is a prime number, \( 1 \le k \le 2 \).

• Subtask 1 (10 pts): \( m \le 20 \).
• Subtask 2 (25 pts): \( k = 1 \).
• Subtask 3 (15 pts): \( n = m \le 30 \).
• Subtask 4 (10 pts): \( m \le 30 \).
• Subtask 5 (15 pts): \( m \le 40 \).
• Subtask 6 (10 pts): \( m \le 70 \).
• Subtask 7 (15 pts): \( m \le 100 \).

见题面 Input 部分

见题面 Output 部分