P5137 polynomial

Wolfycz really likes polynomials (just kidding).

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.

The first line contains $T$, meaning there are $T$ test cases. Each of the next lines contains four integers $n,a,b,p$.

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

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