#include<bits/stdc++.h>

#define ll long long

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int Mod=1e9+;

struct mat

{

    int mp[][];

    mat(){memset(mp,,sizeof(mp)); }

    mat friend operator *(mat a,mat b)

    {

        mat res;

        rep(k,,) rep(i,,) rep(j,,)

         res.mp[i][j]=(res.mp[i][j]+((ll)a.mp[i][k]*b.mp[k][j]%Mod))%Mod;

        return res;

    }

    mat friend operator ^(mat a,int x)

    {

        mat res;

        rep(i,,) res.mp[i][i]=;

        while(x){

          if(x&) res=res*a; a=a*a; x>>=;

        }return res;

    }

};

int main()

{

    int T,N,A,B,C,D,P,fcy;

    scanf("%d",&T);

    while(T--){

        scanf("%d%d%d%d%d%d",&A,&B,&C,&D,&P,&N);

        if(N==) {printf("%d",A); continue;}

        if(N==) {printf("%d",B); continue;}

        for(int i=,r;i<=N;i=r+){

            int tmp=P/i;

            if(tmp==) r=N;

            else r=min(P/(P/i),N);

            mat ans,base;

            ans.mp[][]=B;ans.mp[][]=A; ans.mp[][]=;

            base.mp[][]=D; base.mp[][]=C; base.mp[][]=tmp;

            base.mp[][]=base.mp[][]=;

            ans=(base^(r-i+))*ans;

            if(r==N) fcy=ans.mp[][];

            else B=ans.mp[][],A=ans.mp[][];

        }

        printf("%d\n",fcy);

    }

    return ;

}