题目描述

给定一个$N \\times M$大小的方格，每个方格内都有一个范围在$1$到$K$之间（包括$1$和$K$）的整数。对于这$K^{NM}$种将整数填入方格的方式，按照以下定义计算每种方式的值，并计算所有这些值的总和，取模$D$。

• 对于每个方格，找到该方格所在行和列上的$N+M-1$个整数中的最小值。网格的值定义为所有这$NM$个最小值的乘积。

约束条件

• $1 \\leq N,M,K \\leq 100$
• $10^8 \\leq D \\leq 10^9$
• $N,M,K$和$D$为整数。
• $D$是一个质数。

输入

输入通过标准输入给出，格式如下：

$N$ $M$ $K$ $D$

输出

打印所有$K^{NM}$个值的总和，取模$D$后的结果。

示例输入 1

2 2 2 998244353

示例输出 1

35

存在$1$种填充整数的方式，使得$NM$个值的乘积为$16$，存在$4$种填充方式，使得$NM$个值的乘积为$2$，存在$11$种填充方式，使得$NM$个值的乘积为$1$。

示例输入 2

2 3 4 998244353

示例输出 2

127090

示例输入 3

31 41 59 998244353

示例输出 3

827794103