P10613 [PA 2008] Cliquers
Description
Count the number $x$ of essentially different graphs with $n$ vertices such that every connected component is a complete graph.
Compute $m^x \bmod P$, where $P=10^9-401$ is a prime number.
Input Format
One line with two integers, $n$ and $m$.
Output Format
One line with one integer, representing the required result.
Explanation/Hint
**Sample Explanation.**
When $n=3$, the $3$ cases are shown in the figure below. Note that you should output the value of $m^x \bmod P=2^3 \bmod (10^9-401)$.
**Constraints.**
For all testdata, $1\leq n,m\leq 2\times 10^5$.
Translated by ChatGPT 5