Summing Inverses of Prefix Sum Products

Given four integers n, m, k and a prime p, consider all sequences a of length n satisfying:

• Each element satisfies 1 ≤ a_i ≤ m.
• All elements in the sequence are distinct.

For a sequence a, let its prefix sum array be defined as \( s_i = \sum_{j=1}^{i} a_j \) for \(1 \le i \le n\). Define a function \( f(a) \) by:

\[ f(a)=\frac{1}{\prod_{i=k}^{n} s_i} = \frac{1}{s_k\cdot s_{k+1}\cdots s_n}, \quad \text{where } k \in \{1,2\}. \]

Your task is to compute the sum of \( f(a) \) over all such sequences a, and output the result modulo p. It is guaranteed that p is a prime number.

inputFormat

The input consists of a single line containing four space-separated integers:

1. n (the length of the sequence),
2. m (the maximum allowed value in the sequence),
3. k (the starting index for the product, where 1 ≤ k ≤ 2),
4. p (a prime number for taking modulo).

outputFormat

Output a single integer: the sum of \( f(a) \) over all valid sequences, modulo p.

sample

1 1 1 7

1