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$
.
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$
.
$n = 1$
, $2 \leq MOD \leq 10^9+7$
$1 \leq n \leq 10^9$
, $MOD = 10^9+7$
$1 \leq n \leq 10^9$
,$2 \leq MOD \leq 10^9+7$
For each testcase, print the answer in a separate line.
Input | Output |
---|---|
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 |