题目背景
Wolfycz 很喜欢多项式(雾
题目描述
Wolfycz 喜欢研究多项式,尤其喜欢研究 (a+b)n 这样简单的问题,我们知道 (a+b)n=i=0∑n(in)aibn−i,但是 Wolfycz 对这样的式子并不满足,于是他把所有的系数全部改成了 1,即 i=0∑naibn−i,但是 Wolfycz 发现自己太菜了,不会求答案,于是希望你来帮帮他。
UPD:请注意常数因子对程序运行效率的影响。
输入格式
第一行读入 T,表示有 T 组数据。
接下来每一行读入四个整数 n,a,b,p。
输出格式
共 T 行,每行一个整数,表示 (i=0∑naibn−i)modp 后的值。
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
提示
对于30%的数据,T⩽100,n,a,b,p⩽105
对于100%的数据,T⩽105,n,a,b,p⩽1018
UPD:不保证p为质数!!!