题目背景

题目来自原 BZOJ，我们承认题面及原数据的版权均属于原 BZOJ 或将题目授权给 BZOJ 使用的出题人。如果您是版权所有者且认为我们侵犯了您的权益，可联系我们。

题目描述

一个 $n$ 个点的无向图被叫做是一个 symmetric labeled cliquer，当且仅当该图的任意一个连通子图拥有相同的点数，并且任意一个连通子图都是完全图。

现在用 $m$ 种颜色给所有的 $n$ 个点的 symmetric labeled cliquer 染色，结点有标号，可以染相同的颜色。问方案数对 $10^{9}-401$ 取模的结果。

输入格式

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

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

输出格式

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

1
4 2

32

提示

数据保证，$1\leq T\leq 2$，$1\leq n,m\leq 2\times 10^9$。