代码的时间复杂度是正确的 $O(n^{\frac{3}{4}}\log n)$

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-f;
		ch=getchar(); 
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
int T,mod;
int qpow(int a,int b){
	int ans=1,base=a;
	if(b<0) b+=(mod-1);
	while(b){
		if(b&1) ans=(ans*base)%mod;
		base=base*base%mod;
		b>>=1;
	}
	return ans;
}//默认模数快速幂 
int fast_pow(int a,int b,int c){
	int ans=1,base=a;
	while(b){
		if(b&1) ans=ans*base%c;
		base=base*base%c;
		b>>=1;
	}
	return ans;
}//给定模数快速幂 
int f(int x){
	return (1+x)*x/2;
}
const int MAXN=1e5+10,N=1e5;
namespace type0{
	int sum[MAXN],mu[MAXN],inv[MAXN];
	bool vis[MAXN];
	void prepare(){
		sum[0]=inv[0]=1;
		for(int i=1;i<=N;i++)
			sum[i]=sum[i-1]*i%mod;
		for(int i=1;i<=N;i++) mu[i]=inv[i]=1;
		for(int i=2;i<=N;i++){
			if(vis[i]) continue;
			mu[i]=-1;
			for(int j=i*2;j<=N;j+=i){
				vis[j]=1;
				mu[j]=mu[j]*mu[i];
				if(j%(i*i)==0) mu[j]=0;
			}
		}
		for(int d=1;d<=N;d++)
			for(int T=d;T<=N;T+=d)
				inv[T]=(inv[T]*qpow(d,mu[T/d]))%mod;	
		for(int i=1;i<=N;i++)
			inv[i]=(inv[i]*inv[i-1])%mod;
	}
	int top(int A,int B,int C){
		return qpow(sum[A],B*C);
	}
	int Top(int A,int B,int C){
		return top(A,B,C)*top(B,A,C)%mod;
	}
	int down(int A,int B,int C){
		int l=1,r=0,ans=1;
		while(l<=min(A,B)){
			r=min(A/(A/l),B/(B/l));
			ans=(ans*qpow(inv[r]*qpow(inv[l-1],mod-2)%mod,(A/l)*(B/l)%(mod-1)))%mod;
			l=r+1;
		}
		return qpow(ans,C);
	}
	int Down(int A,int B,int C){
		return down(A,B,C)*down(A,C,B)%mod;
	}
	int getans(int A,int B,int C){
		return Top(A,B,C)*qpow(Down(A,B,C),mod-2)%mod;
	}
}
using namespace type0;
namespace type1{
	int sum[MAXN],inv[MAXN];
	void prepare(){
		sum[0]=inv[0]=1;
		for(int i=1;i<=N;i++){
			sum[i]=sum[i-1]*qpow(i,i)%mod;
			inv[i]=1;
		}			
		for(int d=1;d<=N;d++)
			for(int T=d;T<=N;T+=d)
				inv[T]=(inv[T]*qpow(d,type0::mu[T/d]))%mod;	
		for(int i=1;i<=N;i++)
			inv[i]=qpow(inv[i],i*i);
		for(int i=1;i<=N;i++)
			inv[i]=inv[i]*inv[i-1]%mod;
	}
	int top(int A,int B,int C){
		return qpow(sum[A],f(B)%(mod-1)*f(C)%(mod-1));
	}
	int Top(int A,int B,int C){
		return top(A,B,C)*top(B,A,C)%mod;
	}
	int down(int A,int B,int C){
		int l=1,r=0,ans=1;
		while(l<=min(A,B)){
			r=min(A/(A/l),B/(B/l));
			ans=(ans*qpow(inv[r]*qpow(inv[l-1],mod-2)%mod,f(A/l)%(mod-1)*f(B/l)%(mod-1)))%mod;
			l=r+1;
		}
		return qpow(ans,f(C));
	}
	int Down(int A,int B,int C){
		return down(A,B,C)*down(A,C,B)%mod;
	}
	int getans(int A,int B,int C){
		return Top(A,B,C)*qpow(Down(A,B,C),mod-2)%mod;
	}
}
namespace type2{
	int phi[MAXN];//在mod-1意义下的欧拉函数
	int fac[MAXN],sum[MAXN],res[MAXN];//res是在%mod-1的意义下，phi的前缀和
	int cnt[MAXN],qp[MAXN],P[MAXN];
	vector<int> p[MAXN];//这是每一个数的因数 
	bool vis[MAXN];
	void prepare(){
		for(int i=1;i<=N;i++) phi[i]=i;
		for(int i=2;i<=N;i++){
			if(vis[i]) continue;
			phi[i]=i-1;
			for(int j=i*2;j<=N;j+=i){
				vis[j]=1;
				phi[j]=phi[j]*(i-1)/i;
			}
		} 
		sum[0]=fac[0]=1;
		for(int i=1;i<=N;i++){
			fac[i]=fac[i-1]*i%mod;
			sum[i]=qpow(i,phi[i]);
			sum[i]=sum[i-1]*sum[i]%mod;
			res[i]=(res[i-1]+phi[i])%(mod-1);
		}
		for(int i=0;i<=N;i++) cnt[i]=1;
		for(int i=1;i<=N;i++) P[i]=qpow(i,-1);
		for(int i=1;i<=N;i++)
			for(int j=i;j<=N;j+=i){
				if(mu[j/i]>=0) cnt[j]=cnt[j]*qpow(i,type0::mu[j/i])%mod;
				else cnt[j]=cnt[j]*P[i]%mod;
			}
				
		for(int i=1;i<=N;i++)
			cnt[i]=cnt[i-1]*cnt[i]%mod;
		for(int i=1;i<=N;i++) qp[i]=(qp[i-1]+phi[i])%(mod-1);
	}
	int top(int A,int B,int C){
		int l=1,r=0,ans1=1,ans2=1;
		int mn=min(A,min(B,C));
		while(l<=mn){
			r=min(A/(A/l),min(B/(B/l),C/(C/l)));
			ans1=ans1*qpow(fac[A/l],(res[r]-res[l-1]+mod-1)*(B/l)%(mod-1)*(C/l)%(mod-1))%mod;
			l=r+1;
		}
		return ans1%mod;
	}
	int Top(int A,int B,int C){
		return top(A,B,C)*top(B,A,C)%mod;
	}
	int down(int A,int B,int C){
		int ans=1,l=1,r=0;
		int mn=min(A,min(B,C));
		while(l<=mn){
			r=min(A/(A/l),min(B/(B/l),C/(C/l)));
			int L=1,R=0,minx=min(A/l,B/l),pw=1;
			while(L<=minx){
				R=min((A/l)/(A/(l*L)),(B/l)/(B/(l*L)));
				pw=pw*qpow(cnt[R]*qpow(cnt[L-1],-1)%mod,(A/(l*L))*(B/(l*L)))%mod;
				L=R+1;
			}
			ans=ans*qpow(pw,(qp[r]-qp[l-1]+mod-1)%(mod-1)*(C/l)%(mod-1))%mod;
			l=r+1;
		}
		return ans%mod;
	}
	int Down(int A,int B,int C){
		return down(A,B,C)*down(A,C,B)%mod;
	}
	int getans(int A,int B,int C){
		return Top(A,B,C)*qpow(Down(A,B,C),-1)%mod;
	}
}
using namespace type2;
signed main(){
	T=read(),mod=read();
	type0::prepare();
	type1::prepare();
	type2::prepare();
	while(T--){
		int A=read(),B=read(),C=read();
		cout<<type0::getans(A,B,C)<<" "<<type1::getans(A,B,C)<<" "<<type2::getans(A,B,C)<<endl;
	}
	return 0; 
}