题目描述

JOHNKRAM 最近在研究无向图。他认为如果一个无向图的每个连通块都是完全图，并且每个连通块的大小都是相等的，则这个无向图是完美的。

现在 JOHNKRAM 决定用 $m$ 种颜色对图进行染色。他想知道，对于所有 $n$ 个点的带标号完美无向图，染色方案数的总和是多少？答案 $\mathop{\text{mod}} 10 ^ 9 - 401$。

输入格式

第一行两个整数 $n$ 和 $m$，表示图的点数和颜色种数。

输出格式

输出一个整数，表示答案 $\mathop{\text{mod}} 10 ^ 9 - 401$ 的结果。

4 2

32

数据范围与提示

对于 $10\%$ 的数据，$n, m \leq 10$；
对于 $30\%$ 的数据，$n \leq 10 ^ 6$；
对于 $100\%$ 的数据，$1 \leq n \leq 2 \times 10 ^ 9$。