#P3665. maths

    ID: 2860 传统题 3000ms 512MiB 尝试: 172 已通过: 22 难度: 6 上传者: 标签>CF1900提高欧拉定理欧拉函数试除法分解质因数增广状态矩阵矩阵快速幂快速幂快速乘防溢出

maths

Description

已知 An=Kn∗An−1mA_n=K^n * {A_{n-1}}^m 和 A0A_0 求Anmod  pA_n \mod p

Input Format

第一行两个数 TT,pp 表示数据组数和 pp

接下来 TT 行每行 44 个数分别表示 M,A0,K,nM,A_0,K,n

Output Format

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

输入数据

样例输入 #1

1 10000000007
2 2 2 2

样例输出 #1

256

Hint

对于 100100% 的数据

$T=2500 p<=10^12 n,M,A_0,K \le 10^18

p与p与 A_0$ 互质

pp 与 KK 互质。