import java.io.*;

public class Main {

    private final static int MOD = 666013;

    public static void main(String[] args) throws IOException {

        File in = new File("iepuri.in");
        File out = new File("iepuri.out");

        FileReader fileReader = new FileReader(in);
        BufferedReader bufferedReader = new BufferedReader(fileReader);
        int T = 0;
        String line;


        if ((line = bufferedReader.readLine()) != null) {

            String[] strs = line.trim().split("\\s+");
            T = Integer.parseInt(strs[0]);
        }


        int[][] var = new int[T][7];
        int i, j;


        for (i = 0; i < T; i++) {

            if ((line = bufferedReader.readLine()) != null) {

                String[] strs = line.trim().split("\\s+");
                for (j = 0; j < 7; j++) {
                    var[i][j] = Integer.parseInt(strs[j]);
                }
            }
        }

        PrintWriter writer = new PrintWriter(out);

        for (i = 0; i < T; i++) {

            int X = var[i][0];
            int Y = var[i][1];
            int Z = var[i][2];
            int A = var[i][3];
            int B = var[i][4];
            int C = var[i][5];
            int N = var[i][6];
            //int[] dp = new int[N+1];
            //dp[0] = X;
            //dp[1] = Y;
            //dp[2] = Z;
            int curr = 0;

            for (j = 3; j <= N; j++) {

                curr = ((A * Z%MOD + B*Y%MOD)%MOD + C*X%MOD)%MOD;
                X = Y;
                Y = Z;
                Z = curr;

            }
            writer.println(curr%MOD);
        }
        writer.close();
    }
}