#include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 #define LL long long

 const LL maxn=;

 const LL p=(int)1e9+;

 LL n,k,l,r;

 LL ans[maxn]={};

 LL mpow(LL x,LL y){

     LL z=;

     while(y){

         if(y&)z=(z*x)%p;

         x=(x*x)%p;

         y>>=;

     }

     return z;

 }

 int main(){

     scanf("%lld%lld%lld%lld",&n,&k,&l,&r);

     LL a=r/k,b=l/k;if(l%k)++b;

     for(LL i=r-l;i>=;--i){

         LL ww=a/i-b/i; if(b%i==)++ww;

         if(ww<=)continue;

         ans[i]=(mpow(ww,n)-(ww%p)+p)%p;

         for(int j=*i;j<=r-l;j+=i)ans[i]=(ans[i]-ans[j]+p)%p;

     }

     if(b==)ans[]=(ans[]+)%p;

     printf("%lld\n",ans[]);

     return ;

 }