该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

无额外样例。

题目描述

输入四个整数 $n, p, k, r$，求

$$\left( \sum_{i = 0}^\infty C_{nk}^{ik + r} \right) \bmod p, $$

即

$$\left( C_{nk}^{r} + C_{nk}^{k + r} + C_{nk}^{2k + r} + \cdots + C_{nk}^{(n - 1)k + r} + C_{nk}^{nk + r} + \cdots \right) \bmod p $$

的值。

输入格式

第一行有四个整数 $n, p, k, r$，所有整数含义见问题描述。

输出格式

一行一个整数代表答案。

样例1输入

2 11 2 1

样例1输出

8

样例2输入

987654321 998244353 49 25

样例2输出

822485499

说明/提示

对于 $30\%$ 的测试点，$1 ≤ n, k ≤ 30$，$p$ 是质数；
对于另外 $5\%$ 的测试点，$p = 2$；
对于另外 $5\%$ 的测试点，$k = 1$；
对于另外 $10\%$ 的测试点，$k = 2$；
对于另外 $15\%$ 的测试点，$1 ≤ n ≤ 10^3, 1 ≤ k ≤ 50$，$p$ 是质数；
对于另外 $15\%$ 的测试点，$1 ≤ n \times k ≤ 10^6$，$p$ 是质数；
对于另外 $10\%$ 的测试点，$1 ≤ n ≤ 10^9, 1 ≤ k ≤ 50$，$p$ 是质数；
对于 $100\%$ 的测试点，$1 ≤ n ≤ 10^9, 0 ≤ r < k ≤ 50, 2 ≤ p < 2^{30}$。