You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小周最近在玩一款神奇的单项式多项式（monopoly，又译大富翁）游戏。

这个游戏里有 $n$ 件装备，第 $i$ 件装备有 $m$ 个属性，可以用一个 $m$ 维向量 $\alpha_i = (a_1, \dots, a_m)$ 表示。小周已经收集到了所有的装备，转而好奇这个游戏的底层逻辑。她惊讶地发现，每个数据都是用一个取值范围在 $0$ 和 $p - 1$ 间（即 $\in V = \{0, \dots, p - 1\}$，保证 $p$ 是质数）的无符号整数存储的，并且数据会自然溢出，也就是说，数据间的运算是在模 $p$ 意义下进行的。

小周发现这一点后，想要知道她现在有多少件本质不同的装备。对小周来说，如果一件装备的属性能用其他本质不同的装备组合出（也就是说小周可以利用已知本质不同的装备组合出这件装备的效果），那么这件装备就不是本质不同的装备。并且小周会优先将编号小的装备看作一件本质不同的装备。

严格的定义是，小周维护了一个本质不同的装备组成的集合，最开始她放入了编号最小、且属性不是全零的装备。特别的，如果找不到这样的装备，那么小周会认为她没有（有 $0$ 件）本质不同的装备。随后，她会从那件装备开始，按编号从小到大的顺序考察每件装备，如果现在集合形如 $\{\alpha_{i_1}, \dots, \alpha_{i_k}\}$，并且对现在考察的装备 $\alpha_h$，不存在 $b_1, \dots ,b_k\in V$ 使得 $b_1\alpha_{i_1} + \cdots + b_k\alpha_{i_k} = \alpha_h$（注意，所有运算模 $p$），那么第 $h$ 件装备就是一件本质不同的装备，小周会把它放进集合里，反之就不是，小周不会做任何操作。

小周打开了游戏，却发现它停服维护了。公告说，受宇宙射线的影响，服务器里每个数据都均匀随机地异变为了一个可能的值（即在 $V$ 中均匀随机取）。这可把小周吓坏了，她立即联系了客服人员，让他们按照小周的指示，计算出了她现在一共有 $k$ 件本质不同的装备，才安下了心。

但小周未来还要玩这个游戏，所以她想要知道自己这些装备的属性情况。但小周不想再麻烦焦头烂额的工作人员了，她优秀的游戏技巧也使得她不需要知道具体的属性情况。小周只想知道，在她拥有的所有装备的 $nm$ 个属性里，有多少个属性不为 $0$？由于可能的情况有很多很多种，小周算不明白了，她找到了你，希望你能帮她算出所有情况里，平均有多少个属性不为 $0$。小周不想难为你，因为她的游戏账号名称有子串 3579，她只想知道要求的均值模 $10^9 + 3579$ 的结果。

形式化地，可以证明答案可被表示为一最简分数 $\frac{p}{q}$，请你输出一个 $x$ 满足 $0 \le x < 10^9+3579$ 且 $qx \equiv p \pmod {10^9+3579}$。小周保证存在这样的 $x$。另外，$10^9 + 3579$ 是一个质数，同时也不是一个常用或不常用的 NTT 模数，它的原根为 $19$。如果你不知道什么是 NTT 或者不知道什么是原根，你可以忽略这个提示，因为小周不保证这个提示有用。

输入格式

一行四个整数 $n, m, p, k$。

输出格式

一行一个整数，表示答案。

样例 #1

样例输入 #1

3 4 3 1

样例输出 #1

530771136

样例 #2

样例输入 #2

100000 200000 998244353 1

样例输出 #2

123835813

样例 #3

样例输入 #3

2000000009 3000000009 1000000007 1000000009

样例输出 #3

371122534

数据范围

对于全部数据，$1\le n, m, p, k\le 10^{18}$，保证 $k \le \min\{n, m\}$，$p$ 为质数。