题目背景

Alice 正在教她的弟弟 Bob 学数学。

题目描述

每天，Alice 画一个 $n$ 行 $m$ 列的表格，要求 Bob 在格子里填数。

Bob已经学会了自然数 $1$ 到 $k$ 的写法。因此他在每个格子里填 $1 \sim k$ 之间的整数。

Alice 告诉 Bob，如果 Bob 填写完表格的 $n \times m$ 个数以后，每行的数从第 $1$ 列到第 $m$ 列单调不减，并且任意两行至少有一列的数不同，而且以前 Bob 没有填写过相同的表格，那么 Alice 就给 Bob 吃一颗糖果。

Bob想知道，如果每天填写一遍表格，最多能吃到多少颗糖果。

答案对 $p$ 取模。

输入格式

输入只有一行四个整数，分别代表 $n, m, k, p$。

输出格式

输出一行，一个整数，表示答案模 $p$ 后的结果。

1 3 3 10

0

2 2 2 10

6

提示

样例输入输出 1 解释

共有 $10$ 种方案，取模后为 $0$。

数据规模与约定

• 对于 $100\%$ 的数据，保证 $1 \leq n, m \leq 10^5$，$1 \leq k,p \leq 2 \times 10^9$。