$f$ 的异或和要去掉 前面到第 $i$ 位的 $k
转移在注释上
```cpp
#include<bits/stdc++.h>
using namespace std;
const long long int N=70;
long long int f[N][2][2][2],g[N][2][2][2];
// f_{i,a,b,c} i：考虑到第i位， a,b,c 为1时表示 前面到第i位分别和n,m,k的前面到第i位相等时的异或和 为0时表示i位分别比n,m的前面到第i位小和比k的前面到第i位大时的异或和
//f已经去掉 前面到第i位的k
//g_{i,a,b,c} 同上，但是表示对数
long long int n,m,k,T,p;
int main(){
scanf("%lld",&T);
while(T--){
memset(f,0,sizeof(f));
memset(g,0,sizeof(g));
scanf("%lld%lld%lld%lld",&n,&m,&k,&p);
g[62][1][1][1]=1;
for(int i=61;i>=1;i--){//从高位往低位推
long long int x=(n>>(i-1))&1,y=(m>>(i-1))&1,z=(k>>(i-1))&1;// x: n在第i位的数； y:m在第i位的数；z：k在第i位的数
for(long long int a=0;a<2;a++){ //是不是前面到第i位和n的相等
for(long long int b=0;b<2;b++){//是不是前面到第i位和m的相等
for(long long int c=0;c<2;c++){//是不是前面到第i位和k的相等
if(f[i+1][a][b][c] || g[i+1][a][b][c]){//此处是刷表法，从i,a,b,c转移出去
for(long long int xx=0;xx<2;xx++){//转移到第i位的数 是
for(long long int yy=0;yy<2;yy++){//转移到第i位的数 是
long long int zz=xx^yy;// 已知了这一位的数，这一位的异或就知道了
if((a && x<xx)||(b && y<yy)||(c && z>zz)){
continue;
//1.不能让 前面到第i位相等，现在还这一位比n的这一位大
//2.不能让 前面到第i位相等，现在还这一位比m的这一位大
//3.不能让 前面到第i位相等，现在还这一位比k的这一位小
}
long long int aa=(a && x==xx),bb=(b && y==yy),cc=(c && z==zz);
//如果前面到第i位都相等，现在这一位也相等，就是1，需要再看后面的数才能判断大小
//不然就为0，意为在必定在限制之内
//可以发现不会从0转移到1，只会从1转移到0
g[i][aa][bb][cc]+=g[i+1][a][b][c];
//转移 g
g[i][aa][bb][cc]%=p;
f[i][aa][bb][cc]+=f[i+1][a][b][c]+(zz-z+p)%p*((1ll<<(i-1))%p)%p*g[i+1][a][b][c]%p;
//转移 f，后一项中的(zz-z+p)%p*((1ll<<(i-1))%p)%p就是转移的数的每一位都去掉k的那一位后这一位的贡献， g[i+1][a][b][c]为转移的数量
f[i][aa][bb][cc]%=p;
}
}
}
}
}
}
}
printf("%lld\n",f[1][0][0][0]);
//考虑完最后一位,注意到是0~(n-1)和0~(m-1)，所以直接用表示小于n,m的0，当 两个数异或为k的时候，都减了k，就没必要算了，直接算让异或值大于k
}
}
```