这一天，水之女神阿库娅来雾之找冰之妖精琪露诺。“那个蓝色的妖精，听说你有媲美神（我）的智慧，让我来测试一下是不是真的。”于是阿库娅打算和琪露诺玩一个游戏。

开始的时候琪露诺有一个智慧数$k$，阿库娅会说出$n$个数，每说一个数$p$，琪露诺就要将手上的智慧数$k$变成$k$的$p$次方再模$1000000007$，然后告诉阿库娅。注意琪露诺手上的智慧数是一直在变的。

聪明的琪露诺花了一秒钟就用自己的智慧将阿库娅折服了。现在轮到你来试试你是否也像琪露诺一样聪明了。

输入格式

第一行两个数$n,k$,表示阿库娅会说$n$个数，琪露诺开始的智慧数$k$

接下来$n$行，每行一个数为这次阿库娅说出的数。

输出格式

$n$ 行，第 $i$ 行为琪露诺进行完第 $i$ 次操作后智慧数 $k$ 的值。

样例

样例输入

3 5
3
2
3

样例输出

125
15625
697238927

• 样例解释:
• $5^3=125$
• $125^2=15625$
• $15625^3=3814697265625$
• $3814697265625 \quad mod \quad 1000000007=697238927$

数据范围与提示

• $50$% $n \leq 1000$
• $100$% $n \leq 100000$
• $10$% $p \leq 10$
• $30$% $p \leq 1000$
• $100$% $p \leq 1000000000$

• 时间限制：$1000\mathrm{ms}$
• 空间限制：$10240\mathrm{KB}$