问题 1214 --#6056. 「2011福建集训」最大团

1214: #6056. 「2011福建集训」最大团

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

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

题目中的意思是把所有的 symmetric labeled clique 组成一个集合。

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

题目中的无向图是带标号无向图。

输入格式

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

输出格式

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

样例

样例输入

1
4 2

样例输出

32

数据范围与提示

对于100%100\%100%的数据,n,m≤2×109n,m\leq 2\times 10^9n,m2×109

部分测试数据为本站会员自行生成,并非原数据。时限已按照本站测评机速度进行调整。

输入

输出

提示

来源

 

[提交][状态]