HDU6395

#include<cstdio>
#include<iostream>
#include<cstring>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template<typename T>
inline void read(T&x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int p=1e9+7;

struct Matrix{
    int a[3][3];

    inline Matrix(){
        memset(a,0,sizeof(a));
    }

    inline int* operator [](const int &x){
        return a[x];
    }

    inline const int* operator [](const int &x)const {
        return a[x];
    }

    inline Matrix operator *(const Matrix &b)const {
        Matrix ret;
        for(int i=0;i<3;++i){
            for(int j=0;j<3;++j){
                for(int k=0;k<3;++k){
                    ret[i][j]=(ret[i][j]+(ll)a[i][k]*b[k][j])%p;
                }
            }
        }
        return ret;
    }
}g;

inline Matrix qpow(Matrix a,int b){
    Matrix ans;
    for(int i=0;i<3;++i)ans[i][i]=1;
    while(b){
        if(b&1)ans=ans*a;
        a=a*a;
        b>>=1;
    }
    return ans;
}

int A,B,C,D,E,n;

inline void init(int x){
    g[0][0]=D;
    g[0][1]=1;
    g[0][2]=0;
    g[1][0]=C;
    g[1][1]=0;
    g[1][2]=0;
    g[2][0]=x;
    g[2][1]=0;
    g[2][2]=1;
}

int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    int T;r(T);
    while(T--){
        r(A),r(B),r(C),r(D),r(E),r(n);
        Matrix f;
        f[0][0]=B;
        f[0][1]=A;
        f[0][2]=1;
        if(E<=n){
            for(int i=3,j;i<=E;i=j+1){
                j=E/(E/i);
                init(E/i);
                g=qpow(g,j-i+1);
                f=f*g;
            }
            init(0);
            g=qpow(g,n-max(E,2));
            f=f*g;
        }
        else {
            for(int i=3,j;i<=n;i=j+1){
                j=E/(E/i);
                init(E/i);
                if(j<=n)g=qpow(g,j-i+1);
                else g=qpow(g,n-i+1);
                f=f*g;
            }
        }
        printf("%d\n",f[0][0]);
    }
    return 0;
}
/*
2
3 3 2 1 3 5
3 2 2 2 1 4

1
10 15 17 19 15234532 545
*/