maths

时间限制:30s      空间限制:512MB

题目描述

已知An=Kn * An-1m A0 An mod p


输入格式

 
第一行两个数T,p表示数据组数和p
接下来T行每行4个数分别表示M A0 K n


输出格式

 
T行,每行一个数表示答案


样例输入

1 10000000007
2 2 2 2

样例输出

256

提示

对于100%的数据 T=2500 p<=10^12 n,M,A0,K<=10^18 p与A0互质 p与K互质


题目来源

没有写明来源