P9838

非常好的题！赞美出题人。具体讲讲如何想出来这种题。

容易发现直接做非常难做，一是数据范围非常之大，二是这本身就是相当于一个重排一个序列的问题，计数也很困难。

这种题就大概率要从找性质入手（类似 P2150 寿司晚宴），于是先观察样例及解释，如果你注意力比较集中的话，会注意到，$n=3$ 时就已经出现了很多重复的答案值了。

于是思考这个性质是否具有一般性，为什么会有这个性质。我们发现原来的 $f(x)$ 中就有很多重复的值。于是，我们只需要构造出来一个答案最小的序列，再将其中 $\forall i, f(x)=i$ 的 $x$ 重新排顺序，这样序列的答案仍然是最小的。

于是对于 $n$ 比较大的情况，我们就可以直接构造出最小的答案。具体怎么构造呢？显然是要把 $f(x)$ 大的尽可能靠边。模拟这个过程即可，按照 $f(x)$ 从大到小枚举，则 $f(x)$ 的贡献就要乘上 $\sum_{i\in[l,r]}(i\times(n+1-i))$ 以及一些零散的 $i\times(n+1-i)$ 这样的值。上面的式子的求法就是转成 $S(r)-S(l-1),S(x)=\sum_{i\le x}(i\times(n+1-i))=\sum (i\times(n+1)-i\times i)=(n+1)\times \sum i-\sum i^2$ 于是就可以 $O(1)$ 求了。

同时发现我们这个思路和第 $2,3$ 档分的思想相符，也从侧面说明正确性。（bushi）

接下来就是解决 $n$ 比较小的情况了。毛估估一下需要解决的 $n$ 的上界 $\ge20$（其实是 $28$），$n!$ 的暴力不可过。思考状压，但是又大概要 $O(n3^n)$。

此时突然发现，为什么需要状压呢？实际上 $f(x)\le 5$，为什么不能强行记录每个 $f(x)$ 剩余的数量呢？

于是考虑一个类似背包的 dp，设当前 dp 到第 $i$ 位，要求剩下的 $f(x)$ 贡献之和为 $j$，剩下的 $f(x)=k$ 的 $k$ 数量为 $g_k$ 的方案数。这个东西记忆化搜索一下，发现总状态数小于 $11\times6\times4\times2\times2\times28\times10000\approx3\times 10^7$，大概手写一个哈希表就可以过了。

code：

bool Mbe;
ll n,m,k,a[107];
const int base=19260817;
const int p=1e7+7;
il int Mod(int x,int y){
	return x+y>=mod?x+y-mod:x+y;
}
struct HashTable{
	int tot,head[M];
	struct node{
		ll val;int k,nxt;
	}e[N];
	il ll insert(ll x,int k,int y){
		e[++tot]={x,k,head[y]},head[y]=tot;
		return x;
	}
	ll find(int x,int y){
		go(i,x){
			if(e[i].k==y){
				return e[i].val;
			}
		}
		return -1;
	}
}H;
il int getSum(ll x){
	int ret=0;
	ll a=x,b=x+1,c;
	if(a%2==0){
		a/=2;
	}else{
		b/=2;
	}
	ret=Mod(ret,(a%mod)*(b%mod)%mod*((n+1)%mod)%mod);
	a=x,b=x+1,c=2*x+1;
	if(a%2==0){
		a/=2;
	}else{
		b/=2;
	}
	if(a%3==0){
		a/=3;
	}else if(b%3==0){
		b/=3;
	}else{
		c/=3;
	}
	ret=Mod(ret,mod-(a%mod)*(b%mod)%mod*(c%mod)%mod);
	return ret;
}
il int getHash(int x,int y,vector<int> &g){
	int ret=(x*100000+y)%p;
	for(int i:g){
		ret=(1ll*ret*base+i)%p;
	}
	return ret;
}
ll dfs(int u,int s,vector<int> &g){
	if(s<0){
		return 0;
	}
	if(u==n+1){
		return !s;
	}
	int x=getHash(u,s,g);
	ll ret;
	if(~(ret=H.find(x,u*100000+s))){
		return ret;
	}
	ret=0;
	rep(i,1,k){
		if(g[i-1]){
			g[i-1]--;
			ret+=(g[i-1]+1)*dfs(u+1,s-1ll*u*(n+1-u)*i,g);
			g[i-1]++;
		}
	}
	return H.insert(ret,u*100000+s,x);
}
void Yorushika(){
	scanf("%lld%lld",&n,&m);
	bool fl=0;
	int ans=0;
	ll p=1,tmp=n;
	k=0;
	while(tmp){
		a[++k]=(tmp+1)/2;
		tmp-=(tmp+1)/2;
	}
	drep(i,k,1){
		ll x=a[i];
		if(fl){
			ans=Mod(ans,(p%mod)*((n+1-p)%mod)%mod*(i%mod)%mod);
			p++,fl=0,x--;
		}
		ans=Mod(ans,(i128)2*Mod(getSum(p+x/2-1),mod-getSum(p-1))*i%mod);
		p+=x/2,x&=1;
		if(x){
			ans=Mod(ans,(p%mod)*((n+1-p)%mod)%mod*(i%mod)%mod);
			fl=1;
		}
	}
	if(n>28){
		printf("%d\n",ans);
		return;
	}
	vector<int> g;
	tmp=n;
	while(tmp){
		g.eb((tmp+1)/2);
		tmp-=g.back();
	}
	i128 sum=0;
	rep(i,ans,1e9){
		sum+=dfs(1,i,g);
		if(sum>=m){
			printf("%d\n",i);
			return;
		}
	}
}
bool Med;
signed main(){
	cerr<<(&Mbe-&Med)/1048576.0<<'\n';
	int t=1;
		scanf("%d",&t);
	while(t--)
		Yorushika();
}