CodeForces 896D Nephren Runs a Cinema（組合計數+數論+數形結合）

D. Nephren Runs a Cinema

time limit per test：2.5 seconds

memory limit per test：256 megabytes

input：standard input

output：standard output

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 thatyuan

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

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 modulop.

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

Input

4 97 2 3

Output

13

Input

4 100 0 4

Output

35

Note

We use A, B and C to indicate customers with 50-yuan notes, customers with 100-yuan

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 are3 50-yuan notes left are AAAC, AACA, ACAA and CAAA. So there are13 different queues satisfying the first sample. Similarly, there are35

        非常巧妙的一道綜合數學題……

        大緻題意：電影院有三種方式買票，要麼花五十元買票進去，要麼用卡不用錢，要麼給一百元然後找五十元。然後一開始賣票的人沒有錢找，然後問你總共有多少種方案，可以使得賣票的人不會出現沒錢可找，且最後剩餘的50元錢的張數在區間[l,r]之間。

        首先，我們考慮簡化版的問題，先不考慮用卡消費的方式，而且最後剩餘的五十元錢張數為0。在這種情況下，依稀記得哪個學長講過，對應可以轉化到坐标軸上，人初始時在原點。然後五十元的相當于向前向上走一個機關，然後一百元對應向前向下走一個機關，要求最後從原點(0,0)走到(n,0)。那麼顯然在不考慮沒錢找的情況下，方案數為C(n,n/2)，即向上走和向下走的次數要相同。接下來再考慮這個不合法的情況，相當于走的過程中不能低于x軸。這裡我們可以考慮對稱性，對于一個不合法方案，我們能找到第一個不合法點，設為(a,-1)，如果我們以y=-1為對稱軸，把a之前的所有路線對稱一邊，那麼顯然路線變成了一條從(0,-2)到(n,0)的路線。具體例子可以見下圖。仔細分析後發現，任何一條從(0,-2)到(n,0)的路線都能夠對應一條不合法的方案，是以這個從(0,-2)到(n,0)的路線條數即為不合法方案數。是以，方案數為C(n,n/2)-C(n,n/2-1)

        然後，現在要求最後的五十元錢的張數要在區間[l,r]之間，那麼無非就是改變一下最後的終點而已。可以得到最後的表達式：C(n,(n-l-1)/2)-C(n,(n-min(r,n))/2)也可以寫成C(n,(n+l+1)/2)-C(n,(n+min(r,n))/2)。最後加上刷卡的情況，這個更好說，相當于n次移動中，有那麼幾次沒有動，于是我們可以枚舉有i次用卡，即i次沒有動，對應選取這i個位置的方案數有C(n,i)種，那麼相當于就是可以走剩下的n-i步達到之前的條件。總的來說就是ΣC(n,i)*(C(n-i,(n-i+l+1)/2)-C(n-i,(n-i+min(r,n-i))/2))。

#include<bits/stdc++.h>
#define LL long long
#define N 100010
using namespace std;

LL inv[N],fac[N],p[N],t[N][20];
int n,l,r,P,tot,Phi;

int phi(int k)                                    //歐拉定理需要求P的phi
{
    int i,s;
    s = k;
    for(i = 2;i * i <= k; i++)
    {
        if(k % i == 0) s = s / i * (i - 1);
        while(k % i == 0) k /= i;
    }
    if(k > 1) s = s / k * (k - 1);
    return s;
}

LL qpow(LL a,LL b,LL mod)                            //qpow
{
    LL res=1;
    while(b)
    {
        if (b&1) res=res*a%mod;
        b>>=1; a=a*a%mod;
    }
    return res;
}


void init()
{
    LL x=P;
    Phi=phi(P);
    for(int i=2;(LL)i*i<=x;i++)                        //對P進行質因數分解
    {
        if (x%i) continue;
        while(x%i==0) x/=i;
        p[++tot]=i;
    }
    if (x>1) p[++tot]=x;
    inv[0]=inv[1]=1;
    fac[0]=fac[1]=1;
    for(int i=2;i<N;i++)
    {
        x=i;
        for(int j=1;j<=tot;j++)
        {
            t[i][j]=t[i-1][j];                        //由于是階乘，是以要繼承上一個數字的資訊
            if (x%p[j]) continue;
            while(x%p[j]==0) x/=p[j],t[i][j]++;                //尋找公共質因子，并記錄指數
        }
        fac[i]=fac[i-1]*x%P;                        //對剩下的東西求階乘、逆元
        inv[i]=qpow(fac[i],Phi-1,P);                    //歐拉定理求逆元
    }
}

LL C(int n,int m)
{
    LL res=0;
    if (n<m) return 0;
    if (m==0) return 1;
    res=fac[n]*inv[m]%P*inv[n-m]%P;
    for(int i=1;i<=tot;i++)
        res=res*qpow(p[i],t[n][i]-t[m][i]-t[n-m][i],P)%P;        //求組合數的時候，把少乘的公共質因子乘回去
    return res;
}

int main()
{
    scanf("%d%d%d%d",&n,&P,&l,&r);
    init(); LL ans=0;
    for(int i=0;i<=n;i++)
    {
        int m=n-i;
        ans=(ans+C(n,i)*(-C(m,(m+min(r,m)>>1)+1)+C(m,m+l+1>>1))%P)%P;
    }

    printf("%I64d\n",ans);
    return 0;
}