题目描述

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

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

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

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

输入格式

第一行读入一个数 $T$，表示数据组数。

接下来每行包含两个数 $n,m$，如题所述。

输出格式

输出包含 $T$ 行，每行输出答案。

1
4 2

32

提示

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