#2143. 「SHOI2017」组合数问题

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: cyand1317

题目描述

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

\mathrm{C}_n^m = \frac {n!} {m! \ (n − m)!}

其中 n! = 1 \times 2 \times \cdots \times n 。(特别地,当 n = 0 时, n! = 1 ;当 m > n 时, \mathrm{C}_n^m = 0 。)

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

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

\left( \mathrm{C}_{nk}^{r} + \mathrm{C}_{nk}^{k + r} + \mathrm{C}_{nk}^{2k + r} + \cdots + \mathrm{C}_{nk}^{(n - 1)k + r} + \mathrm{C}_{nk}^{nk + r} + \cdots \right) \bmod p

的值。

输入格式

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

输出格式

一行一个整数代表答案。

样例

样例输入 1

2 10007 2 0

样例输出 1

8

样例解释 1

\mathrm{C}_4^0 + \mathrm{C}_4^2 + \mathrm{C}_4^4 + \cdots = 1 + 6 + 1 = 8

样例输入 2

20 10007 20 0

样例输出 2

176

数据范围与提示

对于 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