#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define int LL
const int N=71,mod=1e9+7,inv2=5e8+4;
int k,n=65,a[N],b[N];
LL l,r,f[N][2][2][2];
LL dfs(int x,int o1,int o2,int p){
    if(x==0){
        return p;
    }
    if(f[x][o1][o2][p]!=-1) return f[x][o1][o2][p];
    LL res=0;
    int l1=(o1?a[x]:k-1),l2=(o2?b[x]:k-1);
    for(int i=0;i<=l1;i++){
        for(int j=0;j<=l2;j++){
            res+=dfs(x-1,(o1 && (i==l1)),(o2 && (j==l2)),(p && (i>=j)));
            res%=mod;
        }
    }
    res=(res+mod)%mod;
    return (f[x][o1][o2][p]=res);
}
LL get(LL l,LL r){
    for(int i=1;i<=n;i++){
        a[i]=r%k;
        r/=k;
    }
    for(int i=1;i<=n;i++){
        b[i]=l%k;
        l/=k;
    }
    memset(f,-1,sizeof(f));
    return dfs(n,1,1,1);
}
LL qSum(LL x){
    return (x*(x+1)%mod*inv2)%mod;
}
signed main(){
    ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    freopen("nzq.in","r",stdin);
    freopen("nzq.out","w",stdout);
    int T=1;
    cin>>T>>k;
    while(T--){
        cin>>r>>l;
        LL ans=-get(l,r);
        l%=mod,r%=mod;
        if(r>=l){
            (ans+=qSum(l+1))%=mod;
            (ans+=(r-l)*(l+1)%mod)%=mod;
        }else{
            (ans+=qSum(r+1))%=mod;
        }
        ans=(ans+mod)%mod;
        cout<<ans<<'\n';
    }
    cerr<<1.0*clock()/CLOCKS_PER_SEC<<'\n';
    return 0;
}

感觉没问题，但是就是没过，然后弘文了