Description

Wolfycz 喜欢研究多项式，尤其喜欢研究 $(a+b)^n$ 这样简单的问题，我们知道 $(a+b)^n=\sum\limits_{i=0}^n\binom{n}{i}a^ib^{n-i}$，但是 Wolfycz 对这样的式子并不满足，于是他把所有的系数全部改成了 $1$，即 $\sum\limits_{i=0}^na^ib^{n-i}$，但是 Wolfycz 发现自己太菜了，不会求答案，于是希望你来帮帮他。

UPD：请注意常数因子对程序运行效率的影响。

Input Format

第一行读入 $T$，表示有 $T$ 组数据。

接下来每一行读入四个整数 $n,a,b,p$。

Output Format

共 $T$ 行，每行一个整数，表示 $(\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

对于$30\%$的数据，$T\leqslant 100,n,a,b,p\leqslant 10^5$

对于$100\%$的数据，$T\leqslant 10^5,n,a,b,p\leqslant 10^{18}$

UPD：不保证$p$为质数！！！