Fun With Functions

Limits 1s, 512 MB

Let's define a function ff:

f(x)=ax+bf(x) = ax + b

We know, f2(x)=f(f(x))f^2(x) = f(f(x)) and f3(x)=f(f(f(x)))f^3(x) = f(f(f(x))). We can write a generalized form, fn(x)=f(fn1(x))f^n(x) = f(f^{n-1}(x)), where n>1n > 1.

You will be given five integers: aa, bb, nn, mm, and MODMOD. Find the value of x=1mfn(x)\sum_{x = 1}^{m}f^n(x). As the answer can be huge, print it modulo MODMOD.

Input

First line contains an integer tt (1t1000001 \leq t \leq 100000), denoting the number of testcases.

Each tescase contains five integers aa,bb, nn, mm and MODMOD.

For all subtasks, 1a,b,m1091 \leq a,b,m \leq 10^9.

Subtasks:

Output

For each testcase, print the answer in a separate line.

Sample

InputOutput
4
2 3 1 1 100000000
2 3 1 3 100000000
1 3 1 3 100000000
2 3 2 3 100000000
5
21
15
51