题意不再赘述。
优先枚举的应该是\(VIP\)用户，枚举范围应该是\([0,n-l]\)
之后总客户数为\(s=n-i\) 再考虑枚举\(100\)的总人数为\(x\) 则要求\(s-2x\in [l,r]\)
这部分方案数应该为从\((0,0)\)到达\((s-x,x)\)且不越过\(y=x\)的方案数。
利用折线法求出方案数为\(C(s,x)-C(s,x-1)\)
由\(s-2x\in [l,r]\)可以解出\(x\in [L,R]\)
则总方案数为\(\sum_{x=L}^RC(s,x)-C(s,x-1)=C(s,R)-C(s,L-1)\)
再利用组合数把\(VIP\)用户合在一起即可。组合数需要特殊处理。
//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<ctime>
#include<cctype>
#include<queue>
#include<deque>
#include<stack>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<string>
#include<ctime>
#include<cmath>
#include<cctype>
#include<cstdlib>
#include<queue>
#include<deque>
#include<stack>
#include<vector>
#include<algorithm>
#include<utility>
#include<bitset>
#include<set>
#include<map>
#define ll long long
#define db double
#define INF 1000000000
#define inf 100000000000000000ll
#define ldb long double
#define pb push_back
#define put_(x) printf("%d ",x);
#define putl_(x) printf("%lld ",x);
#define get(x) x=read()
#define putl(x) printf("%lld\n",x)
#define rep(p,n,i) for(int i=p;i<=n;i+=1)
#define fep(n,p,i) for(int i=n;i>=p;--i)
#define go(x) for(int i=lin[x],tn=ver[i];i;tn=ver[i=nex[i]])
#define pii pair<int,int>
#define mk make_pair
#define gf(x) scanf("%lf",&x)
#define pf(x) ((x)*(x))
#define uint unsigned long long
#define ui unsigned
#define sq sqrt
#define x(w) t[w].x
#define r(w) t[w].r
#define id(w) t[w].id
#define R(w) s[w].r
#define yy p<<1|1
#define zz p<<1
#define sum(w) t[w].sum
#define mod 1000000007
#define sc(A) scanf("%d",&A)
#define scs(A) scanf("%s",A);
#define put(A) printf("%d\n",A)
#define min(x,y) (x>=y?y:x)
#define max(x,y) (x>=y?x:y)
#define sub(x,y) (x-y<0?x-y+mod:x-y)
#define EPS 1e-7
using namespace std;
const int MAXN=100010,G=(mod+1)>>1;
int n,m,cc,kk,l,r,L,R,top;
int fac[MAXN],v[MAXN][30],inv[MAXN];
int p[MAXN];
inline int ksm(int b,int p)
{
int cnt=1;
while(p)
{
if(p&1)cnt=(ll)cnt*b%cc;
b=(ll)b*b%cc;p=p>>1;
}
return cnt;
}
inline int C(int n,int m)
{
if(m>n)return 0;
if(m<0)return 0;
if(m==0)return 1;
int ww=(ll)fac[n]*inv[m]%cc*inv[n-m]%cc;
rep(1,top,i)
{
v[n][i]=v[n][i]-v[m][i]-v[n-m][i];
int cnt=v[n][i];
while(cnt)ww=(ll)ww*p[i]%cc,--cnt;
v[n][i]+=v[m][i]+v[n-m][i];
}
return ww;
}
signed main()
{
//freopen("1.in","r",stdin);
sc(n);sc(m);sc(l);sc(r);kk=cc=m;
if(m==1){puts("0");return 0;}
for(int i=2;i*i<=m;++i)
{
if(m%i==0)
{
p[++top]=i;
kk=kk/i*(i-1);
while(m%i==0)
{
m/=i;
}
}
}
if(m>1){p[++top]=m;kk=kk/m*(m-1);}
fac[0]=inv[0]=inv[1]=fac[1]=1;
rep(2,n,i)
{
int x=i;
rep(1,top,w)
{
v[i][w]=v[i-1][w];
while(x%p[w]==0)
{
x/=p[w];
++v[i][w];
}
}
fac[i]=(ll)fac[i-1]*x%cc;
inv[i]=ksm(fac[i],kk-1);
}
int ans=0;
rep(0,n-l,i)
{
int s=n-i;
R=(s-l)/2;
L=max(0,(s-r+1)/2);
if(L>R)continue;
int w=((ll)C(s,R)-C(s,L-1)+cc)%cc;
ans=(ans+(ll)w*C(n,i))%cc;
}
put(ans);
return 0;
}