← 返回题目列表

AtCoder · agc039_f

F. 最小乘积和

中文机器翻译题面 查看原题

分数: 2000 点

问题陈述

对于每个 K^{NM} 之间写入整数的方法 1 和 K (含)在方格网格中的每个方格中 N 行和 M 列,找到下面定义的值,然后计算所有这些值的总和 K^{NM} 值,模数 D.

  • 对于每个 NM 方格,找出其中的最小值 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 产品的方式 2,和 11 产品的方式 1.


示例输入 2

2 3 4 998244353

示例输出 2

127090

示例输入 3

31 41 59 998244353

示例输出 3

827794103