#1222. zxh的龙王与龙马

龙王 (龍王) 和龙马 (龍馬) 原本是将棋中的两个棋子, 分别由飞车 (飛車) 和角行 (角行) 升变而来, 日本将棋联盟的龙王 (竜王) 头衔就是源自于龙王这枚棋子. 万恶资本家 Sheauhaw 对他们使用了鼠符咒, 让他们化作实体加入 Sheauhaw 的后宫管理系统, 并给予了他们更强大的升变能力.

龙王在某一个评价系统中, 升变前的初始能力值为 $a$. 每升变一次, 其能力值就会产生变化. 显然, $1$ 级能力值 $R(1)=a$. Sheauhaw 研究发现, $k$ 级能力值 $R(k)=a^{R(k-1)}$.

现在 Sheauhaw 想问, 龙王在该评价系统中, $n$ 级能力值 $R(n)$ 是多少. 由于这个值显然过于庞大, 在现在 Sheauhaw 已经知道答案的情况下, 你只需要计算 $R(n)$ 对结构系数 $p$ 取模后的答案即可. 龙马的能力值一般与龙王的能力值成正比, 不需要你计算.

第一行两个整数 $T,p$, 表示数据组数和结构系数.

每组数据输入一行, 一行输入两个整数 $a,n$, 分别表示初始能力值同埋所求等级.

每组数据输出一行, 一行一个整数 $A$, 表示 $R(n)$ 对 $p$ 取模后的值.

输入样例

1 1000000007
4 2

输出样例

256

$1 \leq T \leq 5\times10^4$

$1 \leq p \leq 1000000007$

$1 \leq a \leq 2^{63}-1$

$1 \leq n \leq 200$