Description

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

现有 $m$ 种颜色和所有含有 $n$ 个点且节点有标号的 symmetric labeled cliquer。我们需要将每个 symmetric labeled cliquer 都染上一种颜色，两个不同的 symmetric labeled cliquer 可以染相同颜色，求方案数对 $10^9-401$ 取模的结果。

Input Format

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

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

Output Format

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

1
4 2

32

Hint

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