#include <fstream>
using namespace std;
unsigned long long z[5];
ifstream in("iepuri.in");
ofstream out("iepuri.out");
unsigned long long iepuri(unsigned long long a,unsigned long long b,unsigned long long c,unsigned long long p)
{
    while (p>=3)
    {
        z[4]=z[1]*c+z[2]*b+z[3]*a;
        z[1]=z[2];
        z[2]=z[3];
        z[3]=z[4];
        p--;
    }
    return z[4];
}
int main()
{
    unsigned long long n,i,v,a,b,c;
    in>>n;
    for (i=1;i<=n;i++)
        {
            in>>z[1];
            in>>z[2];
            in>>z[3];
            in>>a;
            in>>b;
            in>>c;
            in >>v;
            out <<iepuri (a,b,c,v)%666013<<endl;
        }
    return 0;
}