https://www.luogu.com.cn/record/158981493

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;

using ll=long long;

const __int128 mod=1000000007;

__int128 read(){
	__int128 x=0;
	char c=getchar();
	while(c<48||c>57)c=getchar();
	while(c>47&&c<58){
		x=(x<<3)+(x<<1)+c-48;
		c=getchar();
	}
	return x;
}

void print(__int128 x){
	if(x>9)print(x/10);
	putchar(x%10+48);
}

__int128 _,n,m,A[65],B[65],la,lb,k,dp[65][2][2];

__int128 calc(__int128 a,__int128 b){
	if(a>=b)return (b*((b+1)%mod)/2%mod+(a-b+mod)%mod*b%mod)%mod;
	else return a*((a+1)%mod)%mod/2%mod;
}

__int128 dfs(__int128 i,bool f1,bool f2){
	if(dp[i][f1][f2]!=-1)return dp[i][f1][f2];
	dp[i][f1][f2]=0;
	__int128 a=A[i];
	__int128 b=B[i];
	if(f1==1&&f2==1)dp[i][f1][f2]=dfs(i+1,1,1)&(a>=b);
	else if(f1==1){
		dp[i][f1][f2]=(dp[i][f1][f2]+dfs(i+1,1,1)*min(a+1,b)%mod)%mod;
		dp[i][f1][f2]=(dp[i][f1][f2]+dfs(i+1,1,0)*(a+1)%mod)%mod;
	}
	else if(f2==1){
		if(a-b>0)dp[i][f1][f2]=(dp[i][f1][f2]+dfs(i+1,1,1)*(a-b)%mod)%mod;
		dp[i][f1][f2]=(dp[i][f1][f2]+dfs(i+1,0,1)*(k-b)%mod)%mod;
	}
	else{
		dp[i][f1][f2]=(dp[i][f1][f2]+dfs(i+1,1,1)*calc(a,b)%mod)%mod;
		dp[i][f1][f2]=(dp[i][f1][f2]+dfs(i+1,1,0)*calc(a,k)%mod)%mod;
		dp[i][f1][f2]=(dp[i][f1][f2]+dfs(i+1,0,1)*calc(k,b)%mod)%mod;
		dp[i][f1][f2]=(dp[i][f1][f2]+dfs(i+1,0,0)*calc(k,k)%mod)%mod;
	}
	return dp[i][f1][f2];
}

void work(__int128 x,__int128 a[],__int128 &cnt){
	while(x)a[++cnt]=x%k,x/=k;
}

int main(){
	_=read(),k=read();
	while(_--){
		n=read(),m=read();
		la=lb=0;
		m=min(n,m);
		work(n,A,la);
		work(m,B,lb);
		__int128 c=max(la,lb);
		for(int i=la+1;i<=c;++i)A[i]=0;
		for(int i=lb+1;i<=c;++i)B[i]=0;
		for(int i=1;i<=c;++i){
			dp[i][0][0]=dp[i][0][1]=-1;
			dp[i][1][0]=dp[i][1][1]=-1;
		}
		dp[c+1][1][1]=1;
		dp[c+1][1][0]=0;
		dp[c+1][0][1]=0;
		dp[c+1][0][0]=0;
		__int128 w=0;
		w=(w+dfs(1,0,0))%mod;
		w=(w+dfs(1,0,1))%mod;
		w=(w+dfs(1,1,0))%mod;
		w=(w+dfs(1,1,1))%mod;
		__int128 ans=((m+1)%mod*((n+1)%mod)%mod-w+mod)%mod;
		if(m&1)ans=(ans-m%mod*((m+1)%mod)/2+mod)%mod;
		else ans=(ans-(m/2)%mod*((m+1)%mod)%mod+mod)%mod;
		ans=(ans%mod+mod)%mod;
		print(ans);
		cout << endl;
	}
	return 0;
}