bobo 是线性代数的忠实粉丝！他计划计算 $\mathbb{F}_q^n$ 中 $k$ 维子空间的数量，结果对 $p$ 取模。

对于不熟悉线性代数的读者：

• $\mathbb{F}_q$ 是集合 $\{0, 1, \dots, q - 1\}$，定义了模 $q$ 的加法和乘法；
• $\mathbb{F}_q^n$ 是 $n$ 维向量空间 $\{(x_1, x_2, \dots, x_n) : x_1, x_2, \dots, x_n \in \mathbb{F}_q\}$；
• 子集 $K \subseteq \mathbb{F}_q^n$ 是一个子空间，当且仅当对于所有 $\mathbf{p}, \mathbf{q} \in K$，都有 $\mathbf{p} + \mathbf{q} \in K$；
• 子空间 $K$ 的维数是其极大无关子集的大小；
• 子集 $\{\mathbf{p}_1, \mathbf{p}_2, \dots, \mathbf{p}_k\} \subseteq K$ 被称为线性无关，当且仅当方程 $c_1 \cdot \mathbf{p}_1 + c_2 \cdot \mathbf{p}_2 + \dots + c_k \cdot \mathbf{p}_k = 0$ 仅有解 $c_1 = c_2 = \dots = c_k = 0$。

输入格式

4 个整数 $q, n, k, p$ ($2 \le q \le 10^9, 1 \le k \le n \le 10^9, 2 \le p \le 2 \cdot 10^5$)。

保证 $p$ 和 $q$ 均为质数。

输出格式

一个整数，表示子空间的数量。

样例

样例输入 1

2 3 2 100003

样例输出 1

7