#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

int num,mod;

struct matrix

{

       int a[][];

}origin,answ;

matrix multiply(matrix x,matrix y)//矩阵乘法

{

       matrix temp;

     //  memset(temp.a,0,sizeof(temp.a));

       for(int i=;i<=num;i++)

       {

               for(int j=;j<=num;j++)

               {

                       int ans=;

                       for(int k=;k<=num;k++)

                       {

                               ans+=((x.a[i][k]*y.a[k][j])%mod);

                       }

                       temp.a[i][j]=ans%mod;

               }

       }

       return temp;

}

matrix calc(int n)//n次矩阵快速幂

{

     while(n)

     {

             if(n%==)

                    answ=multiply(origin,answ);

             origin=multiply(origin,origin);

             n/=;

     }

     return answ;

}

int main()

{

    int t,id,a,b,n,m;

    scanf("%d",&t);

    for(id=;id<=t;id++)

    {

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

        num=;

        memset(answ.a,,sizeof(answ.a));

        memset(origin.a,,sizeof(origin.a));

        mod=;

        while(m--)

            mod=mod*;

        answ.a[][]=a;

        answ.a[][]=b;

        origin.a[][]=;

        origin.a[][]=;

        origin.a[][]=;

        origin.a[][]=;

        printf("Case %d: ",id);

        if(n==)printf("%d\n",a%mod);

        else if(n==)printf("%d\n",b%mod);

        else

        {

            calc(n-);

            printf("%d\n",(answ.a[][]+answ.a[][])%mod);

        }

    }

    return ;

}