P7454 [THUSC 2017] 如果奇迹有颜色

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

现在 B 君有一个由 $n$ 个区域组成的环，B 君要用 $m$ 种颜色来染这 $n$ 个区域。 B 君不希望在这 $n$ 个区域中存在连续 $m$ 个区域恰好出现所有 $m$ 个颜色。换句话说，对于任意连续 $m$ 个区域，都不能恰好出现所有 $m$ 个颜色。 如果两个方案通过旋转可以变得一模一样，那么我们认为他们是本质相同的； 但是如果两个方案需要通过翻转才能变得一模一样，我们不认为他们是本质相同的。 比如如果 $n=4,m=4$； 我们认为 $1,2,3,4$ 和 $3,4,1,2$ 是本质相同的方案； 我们认为 $1,2,3,4$ 和 $4,3,2,1$ 是本质不同的方案； 我们认为 $1,2,1,2$ 和 $2,1,2,1$ 是本质相同的方案； B 君希望知道满足条件，本质不同的方案数，输出答案对 $10^9+7$ 取模。

从标准输入读入数据。 输入一行包含两个整数 $n,m$，其中 $n$ 表示环的长度，$m$ 表示颜色数。

输出到标准输出。 输出一行一个整数，表示答案对 $10^9+7$ 取模的结果。

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