# include<iostream>

 # include<cstdio>

 # include<cstring>

 # include<algorithm>

 using namespace std;

 struct matrix

 {

     int r,c,m[][];

     matrix(int _r,int _c):r(_r),c(_c){}

 };

 int a,b,n,m;

 int mod[]={,,,};

 matrix multiply(matrix a,matrix b)

 {

     matrix c(a.r,b.c);

     for(int i=;i<=c.r;++i){

         for(int j=;j<=c.c;++j){

             c.m[i][j]=;

             for(int k=;k<=a.c;++k){

                 c.m[i][j]+=(a.m[i][k]*b.m[k][j]);

                 c.m[i][j]%=mod[m-];

             }

         }

     }

     return c;

 }

 matrix matrix_pow(matrix a,int k)

 {

     if(k==){

         for(int i=;i<=a.r;++i)

             for(int j=;j<=a.c;++j)

                 a.m[i][j]=(i==j)?:;

         return a;

     }

     if(k==)

         return a;

     matrix res=matrix_pow(a,k/);

     res=multiply(res,res);

     if(k&)

         res=multiply(res,a);

     return res;

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d%d%d%d",&a,&b,&n,&m);

         if(n==){

             printf("%d\n",a%mod[m-]);

             continue;

         }

         matrix mat(,);

         mat.m[][]=mat.m[][]=mat.m[][]=,mat.m[][]=;

         mat=matrix_pow(mat,n-);

         matrix ans(,);

         ans.m[][]=b,ans.m[][]=a;

         ans=multiply(mat,ans);

         printf("%d\n",ans.m[][]);

     }

     return ;

 }