Fun With Functions

fsshakkhor 21st IUT Computer Program...
Limits 1s, 512 MB

Let's define a function $f$:
$f(x) = ax + b$

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

You will be given five integers: $a$, $b$, $n$, $m$, and $MOD$. Find the value of $\sum_{x = 1}^{m}f^n(x)$.
As the answer can be huge, print it modulo $MOD$.

Input

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

Each tescase contains five integers $a$,$b$, $n$, $m$ and $MOD$

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

Subtask

  • Subtask 1 (10 points): $n = 1$, $2 \leq MOD \leq 10^9+7$
  • Subtask 2 (30 points): $1 \leq n \leq 10^9$, $MOD = 10^9+7$
  • Subtask 3 (60 points):
    $1 \leq n \leq 10^9$,
    $2 \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

Submit

Login to submit.

Statistics

44% Solution Ratio
NirjhorEarliest, Aug '21
Tahmid690Fastest, 0.1s
NirjhorLightest, 1.0 MB
SyedshakilmahmShortest, 474B
Toph uses cookies. By continuing you agree to our Cookie Policy.