Description

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

Bob has learned how to write the natural numbers from $1$ to $k$. Therefore, in each cell he writes an integer between $1 \sim k$.

Alice tells Bob that if, after Bob fills in all $n \times m$ numbers, the numbers in each row are non-decreasing from column $1$ to column $m$, and for any two rows there is at least one column where the numbers are different, and Bob has never filled in an identical table before, then Alice will give Bob a piece of candy.

Bob wants to know: if he fills in the table once per day, what is the maximum number of candies he can get.

The answer is taken modulo $p$.

Input Format

The input contains only one line with four integers, representing $n, m, k, p$.

Output Format

Output one line with one integer, representing the answer modulo $p$.

1 3 3 10

0

2 2 2 10

6

Hint

Explanation of Sample Input/Output 1

There are $10$ valid schemes in total, and after taking modulo, it becomes $0$.

Constraints

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

Translated by ChatGPT 5