polynomial
题目背景
Wolfycz 很喜欢多项式(雾
题目描述
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:请注意常数因子对程序运行效率的影响。
输入输出格式
输入格式
第一行读入 $T$,表示有 $T$ 组数据。
接下来每一行读入四个整数 $n,a,b,p$。
输出格式
共 $T$ 行,每行一个整数,表示 $(\sum\limits_{i=0}^na^ib^{n-i})\bmod p$ 后的值。
输入输出样例
输入样例 #1
5
12 78 35 317
35 57 19 193
94 31 75 571
64 80 14 857
74 16 42 751
输出样例 #1
254
24
283
796
407
说明
对于$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$为质数!!!