题目描述

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

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

输入格式

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

输出格式

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

样例

input

4 2

output

32

数据范围与提示

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