Background

This problem comes from the original BZOJ. We acknowledge that the copyright of the statement and the original testdata belongs to the original BZOJ, or to the problem setter who authorized BZOJ to use it. If you are the copyright owner and believe that we have infringed your rights, please contact us.

Problem Description

An undirected graph with $n$ vertices is called a symmetric labeled cliquer if and only if every maximal connected component of the graph has the same number of vertices, and every maximal connected component is a complete graph.

Now there are $m$ colors and all symmetric labeled cliquer graphs with $n$ labeled vertices. We need to color each symmetric labeled cliquer with one color. Two different symmetric labeled cliquer graphs may have the same color. Find the number of coloring schemes modulo $10^9-401$.

Input Format

The first line contains a positive integer $T$, indicating the number of test cases.

Each of the following lines contains two positive integers $n, m$, with the meaning as described above.

Output Format

Output $T$ lines. For each test case, output the answer on one line.

1
4 2

32

Hint

Constraints guarantee that $1\leq T\leq 2$ and $1\leq n,m\leq 2\times 10^9$.

Translated by ChatGPT 5