题目描述

对于一个 $N$ 行 $M$ 列的网格，每个格子都可以填写一个 $1$ 到 $K$ 之间的整数。对于所有 $K^{NM}$ 种填写方式，计算以下值，并将这些值的总和对 $D$ 取模：

• 对于每个格子，找到与它在同一行或同一列（包括它自身）的所有格子中所填写的整数的最小值。将所有 $NM$ 个格子的最小值相乘，得到一个值。

请输出所有填写方式下上述值的总和对 $D$ 取模的结果。

输入格式

输入为一行，包含四个整数：

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

输出格式

输出所有 $K^{NM}$ 种填写方式下上述值的总和对 $D$ 取模的结果。

样例 1

输入

2 2 2 998244353

输出

35

样例 2

输入

2 3 4 998244353

输出

127090

样例 3

输入

31 41 59 998244353

输出

827794103

说明/提示

限制条件

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

样例解释 1

使 $NM$ 个格子的积为 $16$ 的填写方式有 $1$ 种，积为 $2$ 的填写方式有 $4$ 种，积为 $1$ 的填写方式有 $11$ 种。

由 ChatGPT 4.1 翻译