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

3 2

8

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