Fun With Functions

Let's define a function $f$:

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

Subtasks:

• 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

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