#2445. 最大团

题目描述

一个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组成一个集合

这里的染色是指将每个元素染色，两种方案不同当且仅当有一种元素被染的颜色不一样