记录编号	249330	评测结果	AAAAAAAAAA
题目名称	[SDOI 2016] 储能表	最终得分	100
用户昵称	dydxh	是否通过	通过
代码语言	C++	运行时间	1.560 s
提交时间	2016-04-12 15:55:51	内存使用	0.33 MiB

/*
Problem:bzoj3131;
Language:c++;
by dydxh;
Date:2016.04.09;
*/
#include<algorithm>
#include<iostream>
#include<cstring>
#include<utility>
#include<cstdlib>
#include<cstdio>
#include<string>
#include<vector>
#include<ctime>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define ull unsigned long long
using namespace std;
const int oo=2000000000;
const int maxn=70;
ll T,n,m,k,p,L;
ll I[maxn];
int N[maxn],M[maxn],K[maxn];
inline ll read(){
	ll x=0;bool flag=false;char ch=getchar();
	while(ch>'9' || ch<'0'){if(ch=='-') flag=true;ch=getchar();}
	while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return flag?-x:x;
}
ll F[maxn][2][2][3],G[maxn][2][2][3];
//0 < 1 = 2 >
void Prepare(){
	memset(N,0,sizeof(N));
	memset(M,0,sizeof(M));
	memset(K,0,sizeof(K));
	for(ll t=n;t;t>>=1) N[++N[0]]=t&1;
	for(ll t=m;t;t>>=1) M[++M[0]]=t&1;
	for(ll t=k;t;t>>=1) K[++K[0]]=t&1;
	L=max(N[0],max(M[0],K[0]));
	memset(F,0,sizeof(F));
	memset(G,0,sizeof(G));
}
ll Sum,Num;
void Calc(){
	F[L+1][1][1][1]=1;
	for(int i=L;i>=1;i--){
		for(int x=0,xx;x<=1;x++){
			for(int y=0,yy;y<=1;y++){
				for(int z=0,zz;z<=2;z++){
					if(F[i+1][x][y][z]==0 && G[i+1][x][y][z]==0) continue;
					for(int a=0;a<=1;a++){
						if(x && a>N[i]) continue;
						else if(x) xx=(a==N[i]);
						else xx=0;
						for(int b=0;b<=1;b++){
							if(y && b>M[i]) continue;
							else if(y) yy=(b==M[i]);
							else yy=0;
							int c=a^b;
							if(z==0 || z==2) zz=z;
							else zz=(c==K[i]?1:c>K[i]?2:0);
							F[i][xx][yy][zz]=(F[i][xx][yy][zz]+F[i+1][x][y][z])%p;
							G[i][xx][yy][zz]=(G[i][xx][yy][zz]+G[i+1][x][y][z]+I[i-1]%p*F[i+1][x][y][z]%p*c)%p;
						}
					}
				}
			}
		}
	}
	Num=F[1][0][0][2],Sum=G[1][0][0][2];
}
int main(){
	freopen("menci_table.in","r",stdin);
	freopen("menci_table.out","w",stdout);
	I[0]=1;
	for(int i=1;i<=62;i++) I[i]=I[i-1]<<1;
	T=read();
	while(T--){
		n=read(),m=read(),k=read(),p=read();
		Prepare();
		Calc();
		Sum=(Sum-k%p*Num%p+p)%p;
		printf("%lld\n",Sum);
	}
	//cout<<"Time has passed:"<<1.0*clock()/1000<<"s!"<<endl;
    return 0;
}