import java.util.*;
import java.lang.*;
import java.io.*;
class Main {
private static long solve(int players, int a, int b, int c, int start) {
int strengths[] = new int[players];
strengths[0] = start;
// calculate the strength of each player
for (int i = 1; i < players; i++) {
int prev = strengths[i - 1];
strengths[i] = (a*prev*prev + b*prev + c) % 1000000;
}
// We assemble two teams from the players. The teams choose the next
// member in alternation, and always choose the strongest player. So
// we sort the array, and always pick the top two.
// But actually, we want the difference in strength. Therefore, each
// turn we pick the two strongest players, and sum up their differences.
// Note that due to the sorting, the difference will always be non-
// negative.
// We have to special-case the possibility that there is an odd number
// of players.
long difference = 0; // difference = team1 - team2
for (int i = players - 1; i >= 1; i -= 2) {
difference += strengths[i] - strengths[i - 1];
}
if (players % 2 != 0) {
difference += strengths[0];
}
return difference;
}
public static void main
(String args
[]) { try {
int numberOfTerms
= Integer.
parseInt(sc.
readLine()); for (int i = 0; i < numberOfTerms; i++) {
String fields
[] = sc.
readLine().
trim().
split(" "); int players
= Integer.
parseInt(fields
[0]); int a
= Integer.
parseInt(fields
[1]); int b
= Integer.
parseInt(fields
[2]); int c
= Integer.
parseInt(fields
[3]); int start
= Integer.
parseInt(fields
[4]);
long difference = solve(players, a, b, c, start);
System.
out.
println(difference
); }
e.
printStackTrace(System.
out); }
}
}
aW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgpjbGFzcyBNYWluIHsKCXByaXZhdGUgc3RhdGljIGxvbmcgc29sdmUoaW50IHBsYXllcnMsIGludCBhLCBpbnQgYiwgaW50IGMsIGludCBzdGFydCkgewogICAgICAgIGludCBzdHJlbmd0aHNbXSA9IG5ldyBpbnRbcGxheWVyc107CiAgICAgICAgc3RyZW5ndGhzWzBdID0gc3RhcnQ7CiAgICAgICAgCiAgICAgICAgLy8gY2FsY3VsYXRlIHRoZSBzdHJlbmd0aCBvZiBlYWNoIHBsYXllcgogICAgICAgIGZvciAoaW50IGkgPSAxOyBpIDwgcGxheWVyczsgaSsrKSB7CiAgICAgICAgCWludCBwcmV2ID0gc3RyZW5ndGhzW2kgLSAxXTsKICAgICAgICAgICAgc3RyZW5ndGhzW2ldID0gKGEqcHJldipwcmV2ICsgYipwcmV2ICsgYykgJSAxMDAwMDAwOwogICAgICAgIH0KICAgICAgICAKICAgICAgICAvLyBXZSBhc3NlbWJsZSB0d28gdGVhbXMgZnJvbSB0aGUgcGxheWVycy4gVGhlIHRlYW1zIGNob29zZSB0aGUgbmV4dAogICAgICAgIC8vIG1lbWJlciBpbiBhbHRlcm5hdGlvbiwgYW5kIGFsd2F5cyBjaG9vc2UgdGhlIHN0cm9uZ2VzdCBwbGF5ZXIuIFNvCiAgICAgICAgLy8gd2Ugc29ydCB0aGUgYXJyYXksIGFuZCBhbHdheXMgcGljayB0aGUgdG9wIHR3by4KICAgICAgICAvLyAgICAgQnV0IGFjdHVhbGx5LCB3ZSB3YW50IHRoZSBkaWZmZXJlbmNlIGluIHN0cmVuZ3RoLiBUaGVyZWZvcmUsIGVhY2gKICAgICAgICAvLyB0dXJuIHdlIHBpY2sgdGhlIHR3byBzdHJvbmdlc3QgcGxheWVycywgYW5kIHN1bSB1cCB0aGVpciBkaWZmZXJlbmNlcy4KICAgICAgICAvLyBOb3RlIHRoYXQgZHVlIHRvIHRoZSBzb3J0aW5nLCB0aGUgZGlmZmVyZW5jZSB3aWxsIGFsd2F5cyBiZSBub24tCiAgICAgICAgLy8gbmVnYXRpdmUuCiAgICAgICAgLy8gICAgIFdlIGhhdmUgdG8gc3BlY2lhbC1jYXNlIHRoZSBwb3NzaWJpbGl0eSB0aGF0IHRoZXJlIGlzIGFuIG9kZCBudW1iZXIKICAgICAgICAvLyBvZiBwbGF5ZXJzLgogICAgICAgIAogICAgICAgIEFycmF5cy5zb3J0KHN0cmVuZ3Rocyk7CiAgICAgICAgCiAgICAgICAgbG9uZyBkaWZmZXJlbmNlID0gMDsgLy8gZGlmZmVyZW5jZSA9IHRlYW0xIC0gdGVhbTIKICAgICAgICBmb3IgKGludCBpID0gcGxheWVycyAtIDE7IGkgPj0gMTsgaSAtPSAyKSB7CiAgICAgICAgICAgIGRpZmZlcmVuY2UgKz0gc3RyZW5ndGhzW2ldIC0gc3RyZW5ndGhzW2kgLSAxXTsKICAgICAgICB9CiAgICAgICAgaWYgKHBsYXllcnMgJSAyICE9IDApIHsKICAgICAgICAJZGlmZmVyZW5jZSArPSBzdHJlbmd0aHNbMF07CiAgICAgICAgfQogICAgICAgIAogICAgICAgIHJldHVybiBkaWZmZXJlbmNlOwoJfQogICAgcHVibGljIHN0YXRpYyB2b2lkIG1haW4gKFN0cmluZyBhcmdzW10pIHsKICAgICAgICB0cnkgewogICAgICAgICAgICBCdWZmZXJlZFJlYWRlciBzYyA9IG5ldyBCdWZmZXJlZFJlYWRlcihuZXcgSW5wdXRTdHJlYW1SZWFkZXIoU3lzdGVtLmluKSk7CiAgICAgICAgICAgIGludCBudW1iZXJPZlRlcm1zID0gSW50ZWdlci5wYXJzZUludChzYy5yZWFkTGluZSgpKTsKICAgICAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBudW1iZXJPZlRlcm1zOyBpKyspIHsKICAgICAgICAgICAgICAgIFN0cmluZyBmaWVsZHNbXSA9IHNjLnJlYWRMaW5lKCkudHJpbSgpLnNwbGl0KCIgIik7CiAgICAgICAgICAgICAgICBpbnQgcGxheWVycyA9IEludGVnZXIucGFyc2VJbnQoZmllbGRzWzBdKTsKICAgICAgICAgICAgICAgIGludCBhID0gSW50ZWdlci5wYXJzZUludChmaWVsZHNbMV0pOwogICAgICAgICAgICAgICAgaW50IGIgPSBJbnRlZ2VyLnBhcnNlSW50KGZpZWxkc1syXSk7CiAgICAgICAgICAgICAgICBpbnQgYyA9IEludGVnZXIucGFyc2VJbnQoZmllbGRzWzNdKTsKICAgICAgICAgICAgICAgIGludCBzdGFydCA9IEludGVnZXIucGFyc2VJbnQoZmllbGRzWzRdKTsKICAgICAgICAgICAgICAgIAogICAgICAgICAgICAgICAgbG9uZyBkaWZmZXJlbmNlID0gc29sdmUocGxheWVycywgYSwgYiwgYywgc3RhcnQpOwogICAgICAgICAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKGRpZmZlcmVuY2UpOwogICAgICAgICAgICB9CiAgICAgICAgfSBjYXRjaChFeGNlcHRpb24gZSkgewogICAgICAgICAgICBlLnByaW50U3RhY2tUcmFjZShTeXN0ZW0ub3V0KTsKICAgICAgICB9CiAgICB9Cn0=