#include <iostream>
#include <fstream>

using namespace std;

ifstream in("iepuri.in");
ofstream out("iepuri.out");

const int ne=666013;
int t;

int main(){
in >>t;
while(t--){
	long long int x[10030],a,b,c,n;
	in >>x[0]>>x[1]>>x[2]>>a>>b>>c>>n;

	for(int i=3;i<=n;i++){
		x[i]=x[i-1]*a+x[i-2]*b+x[i-3]*c;
	}
	out <<(x[n]%ne)<<"\n";
}

}