因为不能直接减去 \(nmk\)，先把题目中的式子转化为求 \(i\oplus j \ge k\) 的数的个数与和。
这样就可以进行数位 dp 了。令 \(f_{bt,un,um,lk}\) 表示当前考虑到第 \(bit\) 位，\(n\) 有没有达到上界，\(m\) 有没有达到上界，\(k\) 有没有达到下界的个数，\(g\) 表示的是这些数的总和。然后因为考虑的是有没有到达上/下界，从高向低位进行记搜更简单。
转移是简单的，即 \(f_{bit,un,um,lk}=\sum f_{bit-1,un',um',lk'}\)，\(g_{bit,un,um,lk}=\sum g_{bit-1,un',um'lk'}+(i\oplus j)\times 2^{bit}\times f_{bit-1,un',um',lk'}\)。其中 \(i,j\) 表示行、列的当前枚举的位的值。
为了实现方便，返回值是一个 pair 即可只用一次记搜。
代码：
typedef long long ll;
typedef pair<int,int> pii;
ll n,m,k;int p;
ll pw[65];
pii f[64][2][2][2];int vis[64][2][2][2];
pii dfs(int bit,int un,int um,int lk){
if(bit==-1)return pii(1,0);
if(vis[bit][un][um][lk])return f[bit][un][um][lk];
vis[bit][un][um][lk]=1;
pii &now=f[bit][un][um][lk];
now=pii(0,0);
int bn=n>>bit&1,bm=m>>bit&1,bk=k>>bit&1;
for(int i=0;i<=(un?bn:1);i++)for(int j=0;j<=(um?bm:1);j++){
if(lk&&(i^j)<bk)continue;
pii res=dfs(bit-1,un&(i==bn),um&(j==bm),lk&((i^j)==bk));
now.first=(now.first+res.first)%p,now.second=(now.second+res.first*(i^j)*1ll*pw[bit]+res.second)%p;
}
return now;
}
void solve(){memset(vis,0,sizeof(vis));
scanf("%lld%lld%lld%d",&n,&m,&k,&p);n--,m--;
pw[0]=1;for(int i=1;i<=60;i++)pw[i]=pw[i-1]*2%p;
pii res=dfs(60,1,1,1);
cout<<(res.second-res.first*1ll*(k%p)%p+p)%p<<"\n";
}
int main(){
int T;cin>>T;
while(T--)solve();
return 0;
}