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

    ID: 6347 远端评测题 1000ms 500MiB 尝试: 0 已通过: 0 难度: 7 上传者: 标签>动态规划dp数论数学2017状态压缩状压线性递推递推式

[THUSCH2017] 如果奇迹有颜色

题目背景

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

题目描述

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

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

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

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

比如如果 n=4,m=4n=4,m=4

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

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

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

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

输入格式

从标准输入读入数据。

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

输出格式

输出到标准输出。

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

6 3
44
120 6
615888898

提示

对于 100%100\% 的测试点,1n109,2m71\le n\le 10^9,2\le m\le7 。 | 数据点编号 Id\operatorname*{Id} | nn | mm | | :----------: | :----------: | :----------: | | 1~2 | n10n\le10 | m=Id+2m=\operatorname*{Id}+2 | | 3~8 | n105,nn\le 10^5,n 是质数 | m=Id1m=\operatorname*{Id}-1 | | 9~14 | nn 是质数 | m=Id7m=\operatorname*{Id}-7 | | 15~19 | 无特殊约束 | m=Id13m=\operatorname*{Id}-13 | | 20 | n=635,643,090n=635,643,090 | m=7m=7 |