Background

Wolfycz really likes polynomials (just kidding).

Problem Description

Wolfycz likes studying polynomials, and especially likes simple problems like $(a+b)^n$. We know that $(a+b)^n=\sum\limits_{i=0}^n\binom{n}{i}a^ib^{n-i}$, but Wolfycz is not satisfied with such an expression, so he changes all coefficients to $1$, i.e. $\sum\limits_{i=0}^na^ib^{n-i}$. However, Wolfycz finds that he is not skilled enough and cannot compute the answer, so he hopes you can help him.

UPD: Please pay attention to the impact of constant factors on runtime efficiency.

Input Format

The first line contains $T$, meaning there are $T$ test cases.

Each of the next lines contains four integers $n,a,b,p$.

Output Format

Output $T$ lines. Each line contains one integer, representing the value of $(\sum\limits_{i=0}^na^ib^{n-i})\bmod p$.

5
12 78 35 317
35 57 19 193
94 31 75 571
64 80 14 857
74 16 42 751

254
24
283
796
407

Hint

For $30\%$ of the testdata, $T\leqslant 100,n,a,b,p\leqslant 10^5$.

For $100\%$ of the testdata, $T\leqslant 10^5,n,a,b,p\leqslant 10^{18}$.

UPD: $p$ is not guaranteed to be prime.

Translated by ChatGPT 5