unordered_map 常数很大吗？

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>
void in(T &x){
	char c=getchar();T f=1; x=0;
	while(c<'0'||c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	x*=f;
}
const int Mod=998244353;
ll ksm(ll a,ll b){
	ll res=1;
	while(b){
		if(b&1) res=res*a%Mod;
		a=a*a%Mod; b>>=1;
	}
	return res;
}
int t;
ll n; int m;
unordered_map<ll,ll> f,ctb,val;
ll get(ll a,ll b){
	if(val.count(b)) return val[b];
	return val[b]=ksm(a,b); 
}
void calc(ll sz,int dep,int fail){
	if(sz<=0) return;
	if(f.count(sz)) return;
	if(sz==1){
		ctb[1]=fail;
		f[1]=fail;
		return;
	}
	ll l,r,x=(1ll<<dep-1); l=r=x-1;
	ll nsz=sz-l-r-1;
	if(nsz>x) l+=x,r+=nsz-x;
	else l+=nsz;
	calc(l,dep-1,fail);
	calc(r,dep-1,fail);
	f[sz]=(f[l]*get(m,r)+f[r]*get(m,l)+get(m,sz-1))%Mod*fail%Mod;
	ctb[sz]=(ctb[l]*get(m,r+1)+ctb[r]*get(m,l+1)+(f[l]+get(m,l))*(f[r]+get(m,r))%Mod*fail)%Mod;
}
int wei(ll n){
	int i;
	for(i=-1;n;n>>=1,i++);
	return i;
}
void work(){
	in(n); in(m);
	ll ans=0;
	val.clear();
	ans=n%Mod*((n+1)%Mod)%Mod*ksm(2,Mod-2)%Mod*ksm(m,n)%Mod*m%Mod;
	for(int i=1;i<m;i++){
		f.clear(); ctb.clear();
		calc(n,wei(n),i);
		ans+=Mod-ctb[n];
		ans%=Mod;
	}
	printf("%lld\n",ans);
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	in(t);
	while(t--) work();
	return 0;
}