# 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 $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 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$
$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


### Statistics

44% Solution Ratio

NirjhorEarliest, 1M ago

Tahmid690Fastest, 0.1s

NirjhorLightest, 1.0 MB

SyedshakilmahmShortest, 474B