Description

已知 $A_n=K^n * {A_{n-1}}^m$和 $A_0$ 求$A_n \mod p$

Input Format

第一行两个数 $T$，$p$ 表示数据组数和 $p$

接下来 $T$ 行每行 $4$ 个数分别表示 $M,A_0,K,n$

Output Format

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

输入数据

样例输入 #1

1 10000000007
2 2 2 2

样例输出 #1

256

Hint

对于 $100$ 的数据

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

$p与$A_0$ 互质

$p$ 与 $K$ 互质。