Problem A: #2143. 「SHOI2017」组合数问题

Problem A: #2143. 「SHOI2017」组合数问题

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

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

Cmn=n!m! (nm)!

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

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

(i=0Cik+rnk)modp,

(Crnk+Ck+rnk+C2k+rnk++C(n1)k+rnk+Cnk+rnk+)modp

的值。

输入格式

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

输出格式

一行一个整数代表答案。

样例

样例输入 1

2 10007 2 0

样例输出 1

8

样例解释 1

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

样例输入 2

20 10007 20 0

样例输出 2

176

数据范围与提示

对于 30%30\%30% 的测试点,1≤n,k≤301 \leq n, k \leq 301n,k30ppp 是质数;
对于另外 5%5\%5% 的测试点,p=2p = 2p=2
对于另外 5%5\%5% 的测试点,k=1k = 1k=1
对于另外 10%10\%10% 的测试点,k=2k = 2k=2
对于另外 15%15\%15% 的测试点,1≤n≤103,1≤k≤501 \leq n \leq 10^3, 1 \leq k \leq 501n103,1k50ppp 是质数;
对于另外 15%15\%15% 的测试点,1≤n×k≤1061 \leq n \times k \leq 10^61n×k106ppp 是质数;
对于另外 10%10\%10% 的测试点,1≤n≤109,1≤k≤501 \leq n \leq 10^9, 1 \leq k \leq 501n109,1k50ppp 是质数;
对于 100%100\%100% 的测试点,1≤n≤109,0≤r<k≤50,2≤p≤230−11 \leq n \leq 10^9, 0 \leq r < k \leq 50, 2 \leq p \leq 2^{30} - 11n109,0r<k50,2p2301