Problem Statement

For each of the K^{NM} ways to write an integer between 1 and K (inclusive) in every square in a square grid with N rows and M columns, find the value defined below, then compute the sum of all those K^{NM} values, modulo D.

• For each of the NM squares, find the minimum among the N+M-1 integers written in the square's row or the square's column. The value defined for the grid is the product of all these NM values.

Input

Input is given from Standard Input in the following format:
N M K D

Output

Print the sum of the K^{NM} values, modulo D.

Constraints

• $1 \leq N,M,K \leq 100$
• $10^8 \leq D \leq 10^9$
• N,M,K, and D are integers.
• D is prime.

Sample Input 1

2 2 2 998244353

Sample Output 1

35

We have 1 way to write integers such that the product of the NM values is 16, 4 ways such that the product is 2, and 11 ways such that the product is 1.

Sample Input 2

2 3 4 998244353

Sample Output 2

127090

Sample Input 3

31 41 59 998244353

Sample Output 3

827794103

见题面 Input 部分

见题面 Output 部分