核心思路

本题要求计算所有 $n$ 个点的完美图（每个连通块都是相同大小的完全图）的 $m$ 染色方案数之和。关键在于利用组合数学和中国剩余定理来解决模数下的计数问题。

关键观察

1. 图结构分析：完美图对应于将 $n$ 个点划分成若干个大小为 $d$ 的完全图，其中 $d$ 是 $n$ 的因子

2. 染色方案：每个大小为 $d$ 的完全图需要 $d$ 个不同的颜色，染色方案数为 $m(m-1)\cdots(m-d+1)$

重要公式

计数公式

对于固定的划分大小 $d$（其中 $d \mid n$），对应的方案数为：

$$\frac{n!}{(d!)^{n/d} \cdot (n/d)!} \cdot [m(m-1)\cdots(m-d+1)]^{n/d} $$

其中：

• 第一部分是划分的组合数：将 $n$ 个标号点划分成 $n/d$ 个大小为 $d$ 的完全图的方式数
• 第二部分是染色数：每个完全图需要 $d$ 种不同颜色

总答案

最终答案为所有因子 $d \mid n$ 对应的方案数之和：

$$\text{Answer} = \sum_{d \mid n} \frac{n!}{(d!)^{n/d} \cdot (n/d)!} \cdot P(m,d)^{n/d} $$

其中 $P(m,d) = m(m-1)\cdots(m-d+1)$ 是排列数。

算法核心：中国剩余定理

由于模数 $M = 10^9-401 = 999999599$ 是质数，且可以分解为：

$$M = 2 \times 13 \times 5281 \times 7283$$

算法采用中国剩余定理：

1. 分别在模 $2, 13, 5281, 7283$ 下计算答案
2. 使用中国剩余定理合并结果
3. 最终计算 $m^{\text{总方案数}} \bmod (M+1)$

技术要点

1. Lucas定理扩展：处理大阶乘模小质数的计算
2. 质因数分解：高效计算组合数在质数模下的值
3. 因子枚举：只枚举 $n$ 的因子，避免完全分解