#include <fstream>
#define MOD 666013
using namespace std;
ifstream fi("iepuri.in");
ofstream fo("iepuri.out");
int x,y,z,a,b,c,d,k,t,n;
int main()
{
    fi>>t;
    for(int i=1;i<=t;i++)
    {
        fi>>x>>y>>z>>a>>b>>c>>n;
        k=((z*a)%MOD+(b*y)%MOD+(x*c)%MOD)%MOD;
        for(int j=3;j<=n;j++)
        {
            x=y;
            y=z;
            z=k;
            k=((z*a)%MOD+(b*y)%MOD+(x*c)%MOD)%MOD;
        }
        fo<<z<<"\n";
    }
    return 0;
}