Linear Congruential Generator
Computers are great at performing deterministic actions in quick succession. For example, given a set of clear instructions, computers can process those calculations much faster than humans could.
Random numbers pose a differet problem. There are many situations in which we would want the computer to generate some sort of randomized number - maybe for a simulation testing, or providing randomized testcases for a problem solving website.
What if there was a way to produce numbers that look random in a deterministic way, following a set of clear instructions? For this we will use a technique called a Linear Congruential Generator, which takes a seed value x0 and three parameter values a, c, and m. The random numbers are then generated as follows:
x1 = (a * x0 + c) mod m
x2 = (a * x1 + c) mod m
x3 = (a * x2 + c) mod m
x4 = (a * x3 + c) mod m
x5 = (a * x4 + c) mod m
x6 = (a * x5 + c) mod m
x7 = (a * x6 + c) mod m
x8 = (a * x7 + c) mod m
x9 = (a * x8 + c) mod m
x10 = (a * x9 + c) mod m
...
Let's see what happens when we use a seed value of x0 = 2 and the parameters a = 445, c = 700001 and m = 2097152.
700891 = (445 * 2 + 700001) mod 2097152
120848 = (445 * 700891 + 700001) mod 2097152
2048561 = (445 * 120848 + 700001) mod 2097152
48526 = (445 * 2048561 + 700001) mod 2097152
1322551 = (445 * 48526 + 700001) mod 2097152
2032636 = (445 * 1322551 + 700001) mod 2097152
1350509 = (445 * 2032636 + 700001) mod 2097152
1891034 = (445 * 1350509 + 700001) mod 2097152
1252179 = (445 * 1891034 + 700001) mod 2097152
77224 = (445 * 1252179 + 700001) mod 2097152
...
These look fairly random, but they are all in the range between 0 and m, which may be quite large. To achieve our final random dataset, we will typically take each pseudo-random number mod r to adjust it into the range 0 to r. For example setting r = 51 will yield the following from our example dataset:
49 = 700891 mod 51
29 = 120848 mod 51
44 = 2048561 mod 51
25 = 48526 mod 51
19 = 1322551 mod 51
31 = 2032636 mod 51
29 = 1350509 mod 51
5 = 1891034 mod 51
27 = 1252179 mod 51
10 = 77224 mod 51
Here we have produced ten pseudo-random numbers from a single seed value and three chosen parameters then adjusting them to the range 0 to r, but it should be clear that we could continue on and produce more numbers if we wanted to. Importantly, anybody starting with the same a, c, m, x0, and r values would produce the same numebrs.
Many of the upcoming problems on this site will require you to create your own large datasets of random numbers using a Linear Congruential Generator, rather than being given them directly. In this problem you will be given parameters a, c, and m, a seed value x0, a range limit value r. You will be expected to generate n pseudo-random numbers with those values, then take their average.
Input Data
First line is Q, the quantity of testcases.
Q lines then follow, each in the format n a c m x0 r.
Answer
Should consist of Q values, being the average of the dataset generated in each testcase.
Error should be less than 1e-3.
Example
input data:
2
10 445 700001 2097152 2 51
962871 920 854400 3442882 3084770 594798
answer:
26.8 288283.048