Lakhesh loves to make movies, so Nephren helps her run a cinema. We may call it No. 68 Cinema.
However, one day, the No. 68 Cinema runs out of changes (they don't have 50-yuan notes currently), but Nephren still wants to start their business. (Assume that yuan is a kind of currency in Regulu Ere.)
There are three types of customers: some of them bring exactly a 50-yuan note; some of them bring a 100-yuan note and Nephren needs to give a 50-yuan note back to him/her; some of them bring VIP cards so that they don't need to pay for the ticket.
Now n customers are waiting outside in queue. Nephren wants to know how many possible queues are there that they are able to run smoothly (i.e. every customer can receive his/her change), and that the number of 50-yuan notes they have after selling tickets to all these customers is between l and r, inclusive. Two queues are considered different if there exists a customer whose type is different in two queues. As the number can be large, please output the answer modulo p.
Input
One line containing four integers n (1 ≤ n ≤ 105), p (1 ≤ p ≤ 2·109), l and r (0 ≤ l ≤ r ≤ n).
Output
One line indicating the answer modulo p.
Examples
4 97 2 3
13
4 100 0 4
35
Note
We use A, B and C to indicate customers with 50-yuan notes, customers with 100-yuan notes and customers with VIP cards respectively.
For the first sample, the different possible queues that there are 2 50-yuan notes left are AAAB, AABA, ABAA, AACC, ACAC, ACCA, CAAC, CACA and CCAA, and the different possible queues that there are 3 50-yuan notes left are AAAC, AACA, ACAA and CAAA. So there are 13 different queues satisfying the first sample. Similarly, there are 35 different queues satisfying the second sample.
题意：现在有N个人排队看电影，最开始收费处没有50元额钞票。买票的人可以付100元、50元或者刷卡，但是付100元的时候需要保证收费处能补50元。
问最后收费处还剩L到R张50元的方案数。
思路：如果不考虑刷卡，那就是一个卡特兰数，有刷卡的情况，我们枚举刷卡个数即可。所以我们现在假设不存在刷卡的情况：
首先我们需要知道卡特兰数的扩展--->从（0，0）出发到点（a，b），方案数为C(a+b，a)；其中经过x=y分界线的方案数等效于从（-1，1）到（a，b）的方案数C（a+b，a-1）；所以从（0，0）到（a，b），而且不经过x=y的方案数为C(a+b,a)-C(a+b,a-1);
我们注意到这里的a+b为定值，a和a-1相差1，而[L，R]又是连续区间，所以我们利用前缀和来解决这个问题，最终可以推出：
ans=(C(N,(N-L)/2)-C(N,(N-L)/2-1)) + (C(N,(N-L)/2-1)-C(N,(N-L)/2-2)) +...+ (C(N,(N-R)/2)-C(N,(N-R-1)/2)) =C(N,(N-L)/2)-C(N,(N-R-1)/2);
然后需要解决的问题是除法问题，因为P不一定是质数，但是鉴于N比较小，我们可以手动把所有数拆为不含P因子的数和含P因子的数，然后前者做正常的乘法，除法。后者做加，减法，最后统一快速幂乘。
（也可以用找循环节的方法：把P拆分为多个素数幂的形式，最后用中国剩余定理合并，可以见CQZhangYu的代码，但是这里N比较小，没必要。
#include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;i++) #define ll long long using namespace std; const int maxn=100010; int f[maxn],rev[maxn],P,N,p[20],cnt,num[maxn][20]; int qpow(int a,int x){ int res=1;while(x){if(x&1)res=(ll)res*a%P;a=(ll)a*a%P;x>>=1;}return res; } void solve() { int phi=P,tp=P; f[0]=rev[0]=1; for(int i=2;i<=tp/i;i++){ if(tp%i==0) { p[++cnt]=i; phi=phi/i*(i-1); while(tp%i==0) tp/=i; } } if(tp>1) phi=phi/tp*(tp-1),p[++cnt]=tp; rep(i,1,N) { int x=i; rep(j,1,cnt){ num[i][j]=num[i-1][j]; while(x%p[j]==0) num[i][j]++,x/=p[j]; } f[i]=(ll)f[i-1]*x%P; rev[i]=qpow(f[i],phi-1); } } int C(int x,int y) { if(y<0) return 0; int res=1; res=(ll)f[x]*rev[y]%P*rev[x-y]%P; rep(i,1,cnt) res=(ll)res*qpow(p[i],num[x][i]-num[y][i]-num[x-y][i])%P; return res; } int main() { int L,R,ans=0; scanf("%d%d%d%d",&N,&P,&L,&R); R=min(N,R); solve(); rep(i,0,N-L) ans=(ans+1LL*(C(N-i,(N-i-L)>>1)-C(N-i,(N-i-R-1)>>1))*C(N,i))%P; printf("%d ",ans); return 0; }