Fertilizing

Gyeonggeun wants to be the best bean tree farmer in the world. Working toward that dream, he finally developed fertilizer X, which makes a plant shoot up the moment you sprinkle it. The effect is so strong that he does not trust himself to control it all at once, so he decided to raise the strength of the fertilizer little by little and get used to growing bean trees.

Gyeonggeun has N bean tree seeds. He planted them just now, so every tree has height 0. Over the next D days he fertilizes the trees once a day.

On day i (1 ≤ i ≤ D), a tree that absorbs the fertilizer grows by i. The trees fertilized that day are the $C_i$ trees of lowest current height. When several trees have the same height, the result is the same whichever of them you pick.

Right after fertilizing, Gyeonggeun records the height of the $K_i$-th smallest tree to see how well the trees grew.

His ambition was too big and he planted more bean trees than he can handle. Help him and compute the sum of the heights recorded over the D days.

The first line contains a natural number T, the number of test cases. T test cases follow.

Each test case is one line with five integers N, D, s, a, b separated by spaces (1 ≤ N, D ≤ 100,000, 0 ≤ s, a, b ≤ 100,000).

$C_i$ and $K_i$ are generated from s, a, b as follows. Do the intermediate arithmetic in 64-bit integers.

for (int i = 1; i <= D; i++) {
    Ci = s % N + 1;
    s = (s * a + b) % 1000000007;
    Ki = s % N + 1;
    s = (s * a + b) % 1000000007;
}

For each test case, print the sum of the heights recorded over the D days on one line. The sum can exceed the range of a 32-bit integer.