【问题描述】 Sanae 准备对大结界进行一次连续 n 天的风祭。Sanae 每天可以召唤一种神 风。她一共有 m 种神风可以召唤，但是如果有连续 m 天刮了 m 种不同的神风， 环境就会遭到破坏。现在，Sanae 想知道这 n 天她有多少种召唤神风的方案。 由于答案可能很大，所以你只需要告诉她方案数对 1e9+7 取模的结果即可。

【输入格式】 从 sanae.in 读入数据 两个正整数 n,m，分别代表风祭的天数和 Sanae 能召唤的风的种数。

【输出格式】 输出到文件 sanae.out 中 一个整数，为答案对 1e9+7 取模的结果。

【样例输入 1】

3 3 

【样例输出 1】

21

【样例解释】

方案分别为 (1,1,1),(1,1,2),(1,1,3),(1,2,1),(1,2,2),(1,3,1),(1,3,3) (2,1,1),(2,1,2),(2,2,1),(2,2,2),(2,2,3),(2,3,2),(2,3,3) (3,1,1),(3,1,3),(3,2,2),(3,2,3),(3,3,1),(3,3,2),(3,3,3) 共 21 种

【样例输入 2】

9961 4 

【样例输出 2】

937953164 

【数据规模和约定】

对于 8%的数据，m=2

对于另 16%的数据，$n \le 10,m \le 4$

对于 48%的数据，$n \le 100000,m \le 10$

对于 80%的数据，$n \le 100000,2 \le m \le 100$

对于 100%的数据，$2 \le m \le 100,m \le n \le 10^{16}$

$ DP[i][j] $为前i天，最后连续j天不同时的方案数。

考虑第i+1天时，当前的状态能叠加到哪些状态中。第i+1天选择连续不同的天数 (m-j)种方案， 第i+1天选择倒数[1, j]中的某一天 1种方案。乘法原理与加法原理叠加至新状态。

$$ DP[i+1][j+1] += DP[i][j] * (m-j) $$

$$ DP[i+i][k] += DP[i][j] (k \in [1, j]) $$

使用矩阵快速幂加速过程即可满分。

80分代码

#include<cstdio>
 
const int N = 1e5+10;
const int M = 110;
const int Mod = 1e9+7;
long long int dp[N][M];
 
int main() {
	int n, m;
	scanf("%d %d", &n, &m);
	dp[1][1] = m;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<m && i-j+1>=1; j++) {
			dp[i+1][j+1] += dp[i][j] * (m-j);
			dp[i+1][j+1] %= Mod;
			for(int k=1; k<=j; k++) {
				dp[i+1][k] += dp[i][j];
				dp[i+1][k] %= Mod;
			}
		}
	}
	long long int ans = 0;
	for(int j=1; j<m; j++) {
		ans += dp[n][j];
		ans %= Mod;
	}
	printf("%lld", ans);
	return 0;
}