Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Fun With Functions

By fsshakkhor · 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 t(1t100000)t (1 \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.

Subtask

  • Subtask 1 (10 points): n=1n = 1, 2MOD109+72 \leq MOD \leq 10^9+7
  • Subtask 2 (30 points): 1n1091 \leq n \leq 10^9, MOD=109+7MOD = 10^9+7
  • Subtask 3 (60 points):
    1n1091 \leq n \leq 10^9,
    2MOD109+72 \leq MOD \leq 10^9+7

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

    Discussion

    Statistics


    44% Solution Ratio

    NirjhorEarliest, 1M ago

    Tahmid690Fastest, 0.1s

    NirjhorLightest, 1.0 MB

    SyedshakilmahmShortest, 474B

    Submit

    Login to submit

    Toph uses cookies. By continuing you agree to our Cookie Policy.