最大团

时间限制:10s      空间限制:128MB

题目描述

一个n个点的无向图被叫做是一个symmetric labeled cliquer当且仅当该图的任意一个连通子图拥有相同的点数,并且任意一个连通子图都是完全图。现在用m种颜色给所有的n个点的symmetric labeled cliquer染色,可以染相同的颜色,问方案数对109-401取模的结果。
不超过2组数据。


输入格式

第一行读入一个数,表示数据组数。
接下来每行包含两个数n,m,如题所述。
 


输出格式

输出包含T行,每行输出答案。
 


样例输入

1
4 2
 

样例输出

32
 
对于100%,n,m<=2*10^9。

提示

题目中的意思是把所有的symmetric labeled cliquer组成一个集合
这里的染色是指将每个元素染色,两种方案不同当且仅当有一种元素被染的颜色不一样


题目来源

2011福建集训