这道题，常规做法的突破点在于:（R-L<=1e5）这个条件

那么，如果我们把这个条件去掉，询问数据为：
1000000000 1 1 1000000000
该怎么做呢？

一开始，我们先按套路，将L-R取最大公约数为k，化成 到取最大公约数为1

然后开始做题。

首先，我们先来将答案表达式划出来：

(L和R为化过之后的)

那么根据套路带入莫比乌斯函数的性质

然后更改枚举项，枚举k

然后，我们通过观察可以发现，是可以通过整数分块实现的，于是我们整数分块来搞后面部分，至于前面，我们就需要求u的一个区间之和了，这时，我们想到，我们可以求u的前缀和来算区间之和，而快速求u的前缀和的方法，不正是杜教筛/州阁筛/min25筛么？

于是我们就把这题做好了~

（实现时有些小细节需要注意）

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long 
unordered_map<int,int>sp;
const int N=1e7,mod=1e9+7;
int u[N],zhi[N],e;bool f[N];
inline int ksm(int x,int y){
    int ans=1;
    while(y){
        if(y&1){
            ans=(1LL*ans*x)%mod;
        }
        x=(1LL*x*x)%mod;
        y>>=1;
    }
    return ans;
}
inline void sai(int maxe){
    u[1]=1;
    for(int i=2;i<=maxe;++i){
        if(!f[i]){
            u[i]=-1;zhi[++e]=i;
        }
        for(int j=1;j<=e;++j){
            if(i*zhi[j]>maxe){
                break;
            }
            f[i*zhi[j]]=1;u[i*zhi[j]]=-u[i];
            if(i%zhi[j]==0){
                u[i*zhi[j]]=0;
                break;
            }
        }
    }
    for(int i=2;i<=maxe;++i){
        u[i]+=u[i-1];
    }
}
inline int calc(int x){//杜教筛
    if(x<N){
        return u[x];
    }
    if(sp.find(x)!=sp.end()){
        return sp[x];
    }
    int ans=0;
    for(int r,l=2;l<=x;l=r+1){
        r=(x/(x/l));
        ans+=(r-l+1)*calc(x/l);
    }
    sp[x]=1-ans;
    return 1-ans;
}
signed main(){
    sai(N-1);//预处理，按理说应该处理n^(2/3),不过这题主要复杂度不止杜教筛本身，所以我们尽量预处理大点比较好
    int n,k,L,R;
    scanf("%lld%lld%lld%lld",&n,&k,&L,&R);
    L=ceil(double(L)/k),R/=k;
    if(!R){
        puts("0");
        return 0;
    }
    int ans=0;
    for(int r,l=1;l<=R;l=r+1){//整数分块
        if(L-1<l){//当这个情况时，如果计算(L-1)/((L-1)/l))的话，会导致除0，注意到，这之后(L-1)/l都不变(为0)，所以，我们只需算R/(R/l)即可~
            r=(R/(R/l));
        }else{
            r=min(R/(R/l),(L-1)/((L-1)/l));
        }
        int now=ksm(((R/l)-(L-1)/l),n),fow=calc(r)-calc(l-1);
        ans=(ans+((1LL*now*fow)%mod))%mod;
    }
    ans=(ans+mod)%mod;//注意模成正数
    printf("%lld",ans);
    return 0;
}