P10594 BZOJ2445 Maximum Clique.

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.

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$.

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 $T$ lines. For each test case, output the answer on one line.

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