题目描述

小 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$ 种。

Your Task

给定 $n,m$，计算染色的方案数。

由于答案可能很大，请输出它对 $10^9-401$ 取模后的结果。

输入格式

第一行 $t$ 表示数据组数

对于每组数据，仅一行 $n,m$

输出格式

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

2
4 2
2 3

32
9

数据规模与约定

对于 $100\%$ 的数据，$t \leq 10$，$1 \leq n,m \leq 2\times10^9$。