#P6481. [THUSCH2017] 如果奇迹有颜色

    ID: 5075 传统题 1000ms 512MiB 尝试: 5 已通过: 1 难度: 9 上传者: 标签>组合数学动态规划数论线性代数与代数矩阵快速幂CF2600矩阵生成函数状压DP

[THUSCH2017] 如果奇迹有颜色

[THUSCH2017] 如果奇迹有颜色

题目背景

法本公司曾经是世界最大的化工企业,他们生产的染料颜色非常丰富,有清华紫,心灵黄,原谅绿,会议蓝,高级黑,北大红,相簿白等。

题目描述

现在 B 君有一个由 nn 个区域组成的环,B 君要用 mm 种颜色来染这 nn 个区域。

B 君不希望在这 nn 个区域中存在连续 mm 个区域恰好出现所有 mm 个颜色。换句话说,对于任意连续 mm 个区域,都不能恰好出现所有 mm 个颜色。

连续区域可以跨越环的首尾;当 m>nm>n 时,沿环连续取 mm 个位置会重复经过某些区域。颜色本身有区别,不对颜色编号进行置换合并。

如果两个方案通过旋转可以变得一模一样,那么我们认为他们是本质相同的;

但是如果两个方案需要通过翻转才能变得一模一样,我们不认为他们是本质相同的。

下面仅说明方案在旋转、翻转下的判同规则;这些排列不一定满足前述染色限制。例如,当 n=4,m=4n=4,m=4 时:

我们认为 1,2,3,41,2,3,4 和 3,4,1,23,4,1,2 是本质相同的方案;

我们认为 1,2,3,41,2,3,4 和 4,3,2,14,3,2,1 是本质不同的方案;

我们认为 1,2,1,21,2,1,2 和 2,1,2,12,1,2,1 是本质相同的方案;

B 君希望知道满足条件,本质不同的方案数,输出答案对 109+710^9+7 取模。

输入格式

从标准输入读入数据。

输入一行包含两个整数 n,mn,m,其中 nn 表示环的长度,mm 表示颜色数。

输出格式

输出到标准输出。

输出一行一个整数,表示答案对 109+710^9+7 取模的结果。

样例 #1

样例输入 #1

6 3

样例输出 #1

44

样例 #2

样例输入 #2

120 6

样例输出 #2

615888898

提示

对于 100%100\% 的测试点,1≤n≤109,2≤m≤71\le n\le 10^9,2\le m\le7 。

数据点编号 Id⁡\operatorname*{Id} nn mm
1~2 n≤10n\le10 m=Id⁡+2m=\operatorname*{Id}+2
3~8 n≤105,nn\le 10^5,n 是质数 m=Id⁡−1m=\operatorname*{Id}-1
9~14 nn 是质数 m=Id⁡−7m=\operatorname*{Id}-7
15~19 无特殊约束 m=Id⁡−13m=\operatorname*{Id}-13
20 n=635,643,090n=635,643,090 m=7m=7