Problem Background

Alice is teaching her younger brother Bob mathematics.

Problem Description

Every day, Alice draws a table with $n$ rows and $m$ columns and asks Bob to fill in the numbers.

Bob has learned how to write the natural numbers from $1$ to $k$. Therefore, he fills in each cell with an integer between $1$ and $k$.

Alice tells Bob that if he fills in the $n \times m$ cells such that the numbers in each row are non-decreasing from the first to the last column, and at least one column's number is different between any two rows, and he has not filled in the same table before, then Alice will give Bob a candy.

Bob wants to know how many candies he can get at most if he fills in the table every day.

The answer should be taken modulo $p$.

Input Format

The input consists of a single line with four integers: $n, m, k, p$.

Output Format

Output a single integer, which is the answer modulo $p$.

Sample Input and Output

Sample Input #1

1 3 3 10

Sample Output #1

0

Sample Input #2

2 2 2 10

Sample Output #2

6

Notes

Explanation of Sample Input and Output 1

There are 10 possible schemes, which modulo 10 results in 0.

Data Size and Constraints

• For $100\%$ of the data, it is guaranteed that $1 \leq n, m \leq 10^5$, and $1 \leq k, p \leq 2 \times 10^9$.

见题面 Input 部分

见题面 Output 部分