#2195. 分组

分组

本题没有可用的提交语言。

题目描述

<o:p></o:p>

小Z最近在研究数学,尤其是分组问题最令小Z感兴趣。 <o:p></o:p>

分组问题是指将n个不同的人分到若干组中,使得每个组中的人数一样,求方案数。譬如n=4时,不同的分组方案如下: <o:p></o:p>

1.{1}{2}{3}{4} <o:p></o:p>

2.{1,2}{3,4} <o:p></o:p>

3.{1,3}{2,4} <o:p></o:p>

4.{1,4}{2,3} <o:p></o:p>

5.{1,2,3,4} <o:p></o:p>

小Z自然不满足于此,他还想用m种颜色给这些方案染色,再计算染色的方案数。如n=4 m=2时,一共有5种分组方案,那么答案则是2*2*2*2*2=32种。 <o:p></o:p>

Your Task <o:p></o:p>

给定n m,计算染色的方案数。 <o:p></o:p>

由于答案可能很大,请输出它对10^9-401取模后的结果。 <o:p></o:p>

<o:p></o:p>

输入格式

第一行T表示数据组数 <o:p></o:p>

对于每组数据,仅一行n m <o:p></o:p>

<o:p></o:p>

输出格式

对于每组数据,在一行中输出答案 <o:p></o:p>

<o:p></o:p>

2  4 2  2 3
32 9

数据范围与约定



100%:T≤10,1≤n,m≤2*10^9