1 #include<cstdio>  2 #include<algorithm>  3 #include<string.h>  4 #include<queue>  5 #define LL long long  6 using namespace std;  7 const int Nmax=10;  8 LL n,y,x,s,tmp;  9 int mod; 10 int oula_mod; 11  12 struct Matrix 13 { 14     int n,m; 15     long long map[Nmax][Nmax]; 16     Matrix(int x,int y) 17     { 18         n=x;m=y; 19         for(int i=1;i<=n;i++) 20             for(int j=1;j<=m;j++) 21                 map[i][j]=0; 22     } 23     Matrix operator * (const Matrix b) 24     { 25         Matrix c(n,b.m); 26         if(m==b.n) 27         { 28             for(int i=1;i<=c.n;i++) 29                 for(int j=1;j<=c.m;j++) 30                     for(int k=1;k<=m;k++) 31                         c.map[i][j]=(c.map[i][j]+(map[i][k]*b.map[k][j])%oula_mod)%oula_mod; 32             return c; 33         } 34         printf("error!!!!!!!!!!!!!!\n");     35     } 36 }; 37  38  39 int oula(int n) 40 { 41     int ret=1,i; 42     for(i=2;i*i<=n;i++) 43     { 44         if(n%i==0) 45         { 46             n/=i,ret*=i-1; 47             while(n%i==0) n/=i,ret*=i; 48         } 49     } 50     if(n>1) ret*=n-1; 51     return ret; 52 } 53  54  55  56  57 Matrix get(long long n) 58 { 59     Matrix base(4,4); 60     base.map[1][1]=1;base.map[1][2]=1;base.map[1][3]=0;base.map[1][4]=0; 61     base.map[2][1]=0;base.map[2][2]=4;base.map[2][3]=1;base.map[2][4]=4; 62     base.map[3][1]=0;base.map[3][2]=1;base.map[3][3]=0;base.map[3][4]=0; 63     base.map[4][1]=0;base.map[4][2]=2;base.map[4][3]=0;base.map[4][4]=1; 64     Matrix ans(4,4); 65     for(int i=1;i<=ans.n;i++) 66         ans.map[i][i]=1; 67      68     while(n>0) 69     { 70         if(n & 1) 71             ans=ans*base; 72         base=base*base; 73         n>>=1; 74     } 75      76     return ans; 77 } 78  79 long long get_ans(long long times) 80 { 81     long long ans=1; 82     long long base=x; 83     while(times>0) 84     { 85         if(times & 1) 86             ans=(ans*base)%mod; 87         base=(base*base)%mod; 88         times>>=1; 89     } 90     return ans; 91 } 92  93  94 int main() 95 { 96      97     int t; 98     scanf("%d",&t); 99     while(t--)100     {101         scanf("%lld%lld%lld%lld",&n,&y,&x,&s);102         mod=s+1;103         oula_mod=oula(mod);104         //printf("oula_mod:%d\n",oula_mod);105         Matrix base(4,1);106         base.map[1][1]=0;107         base.map[2][1]=1;108         base.map[3][1]=0;109         base.map[4][1]=0;110         Matrix ans=get(n*y)*base;111         long long mi=ans.map[1][1]+oula_mod;112         //printf("mi:%lld\n",mi );113         //continue;114         printf("%lld\n",get_ans(mi));115     }116     return 0;117 }