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

const int N=2e6+5;
int L,R,n,q,p,r,m,k,fac[N],ifac[N],f[N],prm[N],ct=0,g,pw[N],ipw[N];

int adc(int a,int b){return a+b>=p?a+b-p:a+b;}
int dec(int a,int b){return a<b?a-b+p:a-b;}
int mul(int a,int b){return 1ll*a*b%p;}
void add(int &a,int b){a=adc(a,b);}
void del(int &a,int b){a=dec(a,b);}

int qpow(int a,int b=p-2){
  int res=1;
  while(b){if(b&1) res=mul(res,a);a=mul(a,a),b>>=1;}
  return res;
}

bool chk(int x){
  if(qpow(x,p-1)!=1) return 0;
  for(int i=1;i<=ct;i++)
    if(qpow(x,(p-1)/prm[i])==1) return 0;
  return 1;
}

int findrt(){
  for(int i=2;i<p;i++) if(chk(i)) return i;
  return -1;
}

void init(){
  fac[0]=1;
  for(int i=1;i<p;i++) fac[i]=mul(fac[i-1],i);
  ifac[p-1]=qpow(fac[p-1]);
  for(int i=p-1;i>=1;i--) ifac[i-1]=mul(ifac[i],i);
  
  int x=p-1;
  for(int i=2;i*i<=x;i++){
	if(x%i==0){
	  prm[++ct]=i;
	  while(x%i==0) x/=i;
	}
  }
  if(x!=1) prm[++ct]=x;

  g=findrt();

  pw[0]=1,f[0]=fac[r];
  for(int i=1;i<=p-2;i++)
	pw[i]=mul(pw[i-1],g),f[i]=mul(fac[pw[i]+r-1],ifac[pw[i]-1]);
}

int C(int n,int m){
  if(m<0||n<m) return 0;
  return mul(fac[n],mul(ifac[m],ifac[n-m]));
}

int binom(int n,int m){
  if(m<0||n<m) return 0;
  if(m==0) return 1;
  return mul(C(n%p,m%p),binom(n/p,m/p));
}

int calc(int k){
  if(k>=r) return fac[r];
  int res=dec(0,mul(k+1,f[0]));
  for(int j=1;j<=p-2;j++)
    del(res,mul(f[j],mul(dec(pw[(p-1-j)*(k+1)%(p-1)],1),qpow(dec(pw[p-1-j],1)))));
  return res;
}

int SOLVE(int M){
  if(!M||M<q) return 0;
  m=(M-q)/(p-1),k=(M-q)%(p-1);

  if(!r){
	if((q+m)&1) return dec(0,binom(q-1,m));
	return binom(q-1,m);
  }

  if(!k) k=p-1,--m;
  int res=0;

  res=dec(mul(binom(q,m),calc(k)),mul(binom(q-1,m-1),fac[r]));
  if((q+m)&1) return dec(0,res);
  return res;
}

signed main(){
  /*2024.7.25 H_W_Y QOJ 1285 Stirling Number*/
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  cin>>n>>L>>R>>p;
  q=n/p,r=n%p;init();
  cout<<dec(SOLVE(R),SOLVE(L-1));
  return 0;
}