Dividing into Regions

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
ChefLand develops very fast. Recently, there were a few new cities built, so the total number of cities in ChefLand have become N.
In order to communicate, the cities are connected with N1 bidirectional roads in such a way that there is exactly one way to get from one city to another. In other words, the graph with cities as nodes and roads as edges is a tree.
Now, the King of ChefLand thinks that the country is too big to be ruled by one person, so he decided to split in two parts, each of which will be ruled by one of two his sons. The split should be made by blocking one road. After doing that, there will be two connected parts which will be ruled by sons.
However, not every division is good. In some cases, one of the parts will still be very large, thus, it will be very hard for some of the sons to rule it. So, for every connected part, there's a value called inconvenience. The inconvenience of the part equals to the distance between two most distance cities belonging to this part.
So for every split, there are two inconvenience values that should be calculated. Please help the King to find them!
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
In order not to make this problem I/O related, we will give you the road system in the compressed form. The first and only line of the test case will contain six spaceseparated integers N, A, B, C, D, E with the following meaning:
 The road system contains N cities and N1 roads.
 The i^{th} road (1indexed) connects the cities with the numbers i+1 and ((A + B * (i  1)) % i) + 1 and has the length equal to (C * i + D) % E.
Output
In order not to make this problem I/Orelated, we will ask you the hash function of the answer to each test case.
The hash function is calculated this way:
Constraints
 1 ≤ T ≤ 10^{5}
 2 ≤ N, sum of N ≤ 5 × 10^{6}
 0 ≤ A, B, C, D ≤ 10^{4}
 2 ≤ E ≤ 200
Example
Input: 2 5 1 2 3 4 5 89 189 111 34 7 200 Output: 99116027 515191750
Explanation
Example case 1. The roads are:
 Road connecting cities 1 and 2 with length 2;
 Road connecting cities 2 and 3 with length 0;
 Road connecting cities 3 and 4 with length 3;
 Road connecting cities 4 and 5 with length 1.
If we remove the first road, then the inconveniences of the parts will be equal to 0 and 4. So Q_{1} = 0, Q_{2} = 4.
If we remove the second road, the inconveniences will be equal to 2 and 4. So Q_{3} = 2, Q_{4} = 4.
If we remove the third road, the inconveniences will be equal to 2 and 1. So Q_{5} = 1, Q_{6} = 2.
If we remove the fourth road, the inconveniences will be equal to 5 and 0. So Q_{7} = 0, Q_{8} = 5.
So, we've obtained the sequence Q = (0, 4, 2, 4, 1, 2, 0, 5).
By calculating the hash function, we get 0 × 1000003^{0}+4 × 1000003^{1}+2 × 1000003^{2}+4 × 1000003^{3}+1 × 1000003^{4}+2 × 1000003^{5}+0 × 1000003^{6}+5 × 1000003^{7} mod (10^{9}+7)= 5000105000947004756014371026147026557011640 mod (10^{9}+7) = 99116027
Example case 2. This is just a big test case, so that you could check your solution better.
Author:  xcwgf666 
Tester:  
Editorial  http://discuss.codechef.com/problems/REGIONS 
Tags  bfs, dfs, memoization, snckpb16, tree, xcwgf666 
Date Added:  8062016 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 