A6018. 「2017 山东三轮集训 Day5」Dark
编程题
省选/NOI-
知识点
题目描述
JOHNKRAM 最近在研究无向图。他认为如果一个无向图的每个连通块都是完全图，并且每个连通块的大小都是相等的，则这个无向图是完美的。
现在 JOHNKRAM 决定用 $ m $ 种颜色对图进行染色。他想知道，对于所有 $ n $ 个点的带标号完美无向图，染色方案数的总和是多少？答案 $ \mathop{\text{mod}} 10 ^ 9 - 401 $。
现在 JOHNKRAM 决定用 $ m $ 种颜色对图进行染色。他想知道，对于所有 $ n $ 个点的带标号完美无向图，染色方案数的总和是多少？答案 $ \mathop{\text{mod}} 10 ^ 9 - 401 $。
输入格式
第一行两个整数 $ n $ 和 $ m $，表示图的点数和颜色种数。
输出格式
输出一个整数，表示答案 $ \mathop{\text{mod}} 10 ^ 9 - 401 $ 的结果。
输入输出样例
输入 #1
4 2
输出 #1
32
说明/提示
对于 $ 10\% $ 的数据，$ n, m \leq 10 $；
对于 $ 30\% $ 的数据，$ n \leq 10 ^ 6 $；
对于 $ 100\% $ 的数据，$ 1 \leq n \leq 2 \times 10 ^ 9 $。
对于 $ 30\% $ 的数据，$ n \leq 10 ^ 6 $；
对于 $ 100\% $ 的数据，$ 1 \leq n \leq 2 \times 10 ^ 9 $。