分析

可以设状态 \(f_{l,r,k}\) 表示区间 \([l,r],bit(x\in[l,r])\le k\)的{前缀长度，后缀长度，总方案数}。
合并即找一个 \(mid\)，类似最大子段和的合并。
如何找个 \(mid\) 是解题的关键，关于二进制分治题目，令 \(mid\) 为 highbit 或
lowbit 通常有很好的性质，本题 \(mid\) 为highbit。
设 \(mid=2^m-1\)，其中 \(2^m\) 是 \(n-1\) 的 highbit，转移方程有：
\(f_{0,n-1,k}=merge(f_{0,2^m-1,k},merge(2^m,n-1,k))\)
观察后面状态，发现highbit都为 2^m，考虑去掉这一位 1，转移方程变成：
\(f_{0,n-1,k}=merge(f_{0,2^m-1,k},merge(0,n-1-2^m,k-1))\)
发现 \(l\) 恒等于 0，于是将区间改为长度，即 \(f_{i,k}\) 表示(从0开始)长度为 \(i,bit(x) \le k\) 的{前缀长度，后缀长度，总方案数}。
转移方程改为 \(f_{n,k}=merge(f_{2^m,k},f_{n-2^m,k-1}\)，但此时时间复杂度依然是线性的。
发现转移前部分状态是固定，考虑预处理，设 \(g_{k,i}\) 为 \(bit(x)\le k\)，长度为 \(2^i\) 的状态。
转移方程类比上式有：
\(g_{k,i}=merge(g_{k,i-1},g_{k-1,i-1})\)
于是，时间复杂度变为 \(O(klogn+logn)\)，可以通过此题。

代码

int n,k;

int mul(int x,int y){
	int res=0;
	while(y){
		if(y&1) res=(res+x)%mod;
		x=(x+x)%mod;y>>=1;
	}
	return res;
}

struct state{
	int len,lmx,rmx,ans;
	friend state operator +(state a,state b){
		state c;
		c.lmx=a.lmx;
		if(a.lmx==a.len) c.lmx=max(c.lmx,a.len+b.lmx);
		c.rmx=b.rmx;
		if(b.rmx==b.len) c.rmx=max(c.rmx,b.len+a.rmx);
		c.ans=(a.ans+b.ans+mul(a.rmx,b.lmx))%mod;
		c.len=a.len+b.len;
		return c;
	}
}dp[K][K];

state solve(int n,int k){
	if(n==0) return {0,0,0,0};
	if(k==0) return {n,1,(n==1),1};
	int t;
	for(t=60;~t;t--) if(n>>t&1ll){break;}
	return dp[k][t]+solve(n-(1ll<<t),k-1);
}

void Main(){
	n=rd,k=rd;
	cout<<solve(n,k).ans<<endl;
}

signed main(){
	for(int i=0;i<=60;i++)
		dp[0][i]={1,1,(i==0),1};
	for(int k=1;k<=60;k++){
		dp[k][0]={1,1,1,1};
		for(int i=1;i<=60;i++){
			dp[k][i]=dp[k][i-1]+dp[k-1][i-1];
		}
	}
	int T=rd;
	while(T--) Main();
}