题目描述

一个 $n$ 个点的带标号无向图被称为 symmetric labeled clique，当且仅当满足以下两个条件：

1. 该图的任意一个连通分量拥有相同的点数；
2. 任意一个连通分量都是完全图。

现在用 $m$ 种颜色给所有 $n$ 个点的 symmetric labeled clique 染色（颜色可以重复使用）。两种方案不同，当且仅当存在某个元素被染的颜色不同。

问：染色方案数对 $10^9 - 401$ 取模的结果。

注意：题目中将所有的 symmetric labeled clique 视为一个集合。

输入格式

第一行输入一个整数 $T$，表示数据组数。
接下来 $T$ 行，每行包含两个整数 $n, m$，含义如题所述。

输出格式

输出共 $T$ 行，每行一个整数，表示对应数据组的答案。

样例

输入

1
4 2

输出

32

数据范围与提示

• 对于 $100\%$ 的数据，$n, m \leq 2 \times 10^9$。
• 测试数据中不超过 2 组数据。