分组

小 Z 最近在研究数学，尤其是分组问题最令小 Z 感兴趣。

分组问题是指将 $n$ 个不同的人分到若干组中，使得每个组中的人数一样，求方案数。譬如 $n=4$ 时，不同的分组方案如下：

1. $\{1\}\{2\}\{3\}\{4\}$；
2. $\{1,2\}\{3,4\}$；
3. $\{1,3\}\{2,4\}$；
4. $\{1,4\}\{2,3\}$；
5. $\{1,2,3,4\}$。

小 Z 自然不满足于此，他还想用 $m$ 种颜色给这些方案染色，再计算染色的方案数。如 $n=4$、$m=2$ 时，一共有 $5$ 种分组方案，那么答案则是 $2\times 2\times 2\times 2\times 2=32$ 种。

给定 $n$ 和 $m$，计算染色的方案数。由于答案可能很大，请输出它对 $10^9-401$ 取模后的结果。

输入格式

第一行一个整数 $T$，表示数据组数。

对于每组数据，仅一行两个整数 $n$ 和 $m$。

输出格式

对于每组数据，在一行中输出答案。

样例输入

2

4 2

2 3

样例输出

32
9

样例解释

第一组数据即题目描述中的例子，$n=4$ 时共有 $5$ 种分组方案，答案为 $2^5=32$。

第二组数据中 $n=2$，分组方案只有 $\{1\}\{2\}$ 和 $\{1,2\}$ 两种，答案为 $3^2=9$。

数据范围

对于 $100\%$ 的数据：

• $T\le 10$；
• $1\le n\le 2\times 10^9$，$1\le m\le 2\times 10^9$。

来源与许可

本题题面与测试数据整理自 BZOJ 2313。

样例 1

输入

2

4 2

2 3

输出

32
9