题目描述

给定初始值 $k$ 和操作次数 $n$。

每次操作给定一个数 $p$，将当前的 $k$ 更新为 $k^p mod 1000000007。$ 需要在每次操作后输出当前的 $k$ 值。

输入格式

第一行:两个整数 $n$ 和 $k$，表示操作次数和初始值。

接下来 $n$ 行:每行一个整数 $p$，表示本次操作的指数。

输出格式

$n$ 行:每行一个整数，表示每次操作后的 $k$ 值(即 $k^p mod 1000000007)$。

样例 1 输入

3 5 
3 
2 
3

样例 1 输出

125
15625
697238927

样例 1 解释

• $5^3 =125$

• $125^2 = 15625$

• $15625$

• $3814697265625 mod 1000000007 = 697238927$。

数据范围

• 对于 $50\%$ 的数据，$n ≤ 1000$

• 对于 $100\%$ 的数据，$n ≤ 100000$

• 对于 $10\%$ 的数据，$p ≤ 10$

• 对于 $30\%$ 的数据，$p ≤ 1000$

• 对于 $100\%$ 的数据，$p ≤ 1000000000$