4870 - [Shoi2017]组合数问题

组合数 C_n^m表示的是从 n 个互不相同的物品中选出 m 个物品的方案数。举个例子， 从(1,2,3) 三个物品中选择两个物品可以有 (1,2),(1,3),(2,3)这三种选择方法。根据组合数的定义，我们可以给出计算组合数 C_n^m的一般公式：

C_n^m=\dfrac{n!}{m!(n-m)!}

其中 n! = 1 \times 2 \times \cdots \times n。（特别地，当 n = 0 时，n!=1；当 m > n 时，C_n^m=0。）

小葱在 NOIP 的时候学习了 C_i^j和 k 的倍数关系，现在他想更进一步，研究更多关于组合数的性质。小葱发现，C_i^j是否是 k 的倍数，取决于 C_i^j \bmod k是否等于 0，这个神奇的性质引发了小葱对 \mathrm{mod} 运算（取余数运算）的兴趣。现在小葱选择了是四个整数 n,p,k,r，他希望知道

\sum\limits_{i=0}^{\infty}C_{nk}^{ik+r}\bmod p,

即

(C_{nk}^r+C_{nk}^{k+r}+C_{nk}^{2k+r}+\cdots++C_{nk}^{nk+r}+\cdots )\bmod p

的值。

第一行有四个整数 n, p, k, r，所有整数含义见问题描述。 1 ≤ n ≤ 10^9, 0 ≤ r < k ≤ 50, 2 ≤ p ≤ 2^30 ? 1

一行一个整数代表答案。

对于 30\% 的测试点，1 \leq n, k \leq 30，p 是质数；

对于另外 5\% 的测试点，p = 2；

对于另外 5\% 的测试点，k = 1；

对于另外 10\% 的测试点，k = 2；

对于另外 15\% 的测试点，1 \leq n \leq 10^3, 1 \leq k \leq 50，p 是质数；

对于另外 15\% 的测试点，1 \leq n \times k \leq 10^6，p 是质数；

对于另外 10\% 的测试点，1 \leq n \leq 10^9, 1 \leq k \leq 50，p 是质数；

对于 100\% 的测试点，1 \leq n \leq 10^9, 0 \leq r < k \leq 50, 2 \leq p \leq 2^{30} - 1。