import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintStream;
import java.util.Scanner;

public class Main {

    public static final int MOD = 666013;
    public static PrintStream out;

    public static void printResult(int result) {
        out.println(result);
    }

    public static int remainder(int number) {
        return (number % MOD);
    }

    public static void main(String[] args) throws FileNotFoundException {
        //long startTime = System.nanoTime();
        Scanner in = new Scanner(new File("iepuri.in"));
        out = new PrintStream(new File("iepuri.out"));
        int dataSetCount = in.nextInt();
        in.nextLine();
        for (; dataSetCount > 0; dataSetCount--) {
            String words[] = in.nextLine().split(" ", 7);
            int[] v = new int[3];
            v[0] = Integer.parseInt(words[0]);
            v[1] = Integer.parseInt(words[1]);
            v[2] = Integer.parseInt(words[2]);
            int a = Integer.parseInt(words[3]);
            int b = Integer.parseInt(words[4]);
            int c = Integer.parseInt(words[5]);
            int n = Integer.parseInt(words[6]);
            if (n < 3)
                printResult(v[n]);
            else
                for (int i = 3; ; i++) {
                    int x = remainder(a * v[2]) + remainder(b * v[1]) + remainder(c * v[0]);
                    x = remainder(x);
                    if (i == n) {
                        printResult(x);
                        break;
                    }
                    v[0] = v[1];
                    v[1] = v[2];
                    v[2] = x;
                }
        }
        //long endTime = System.nanoTime();
        //System.out.println("Timp total: " + ((endTime - startTime) / 1000000000d) + " secunde.");
        //System.out.println("Timp maxim infoarena: 0.05 secunde.");
    }
}