### $\text{Description}:$
给定一个长为 $s$ 序列 $a$，如果 $a_1 = \min_{i=1}^{r} a_i$。
令 $a_{s + 1} = a_1$，有 $\forall i ,\left | a_i-a_{i+1} \right | =1$，我们称这个序列是良好的。
给定一个长为 $s$ ($1 \le s \le n$) 单调不降的序列 $b$，如果 $\forall i ,1 \le b_i \le m$ 且将 $b$ 重新排列至少可以得到 $1$ 个良好序列，至多得到 $k$ 个良好序列，我们称 $b$ 是优秀的。
给定 $n,m,k$ 求有多少个优秀的序列。结果对 $1e9+7$ 取模。
数据范围：$1 \le n,m,k \le100$
### $\text{Solution}:$
要求优秀序列的方案数，首先想如何构造出一个这样的序列。但即使求至少 $1$ 良好序列也不好找出一些条件来描述这样的数列。所以我们尝试去构造良好的序列。
如果我们从高位数字开始构造，当考虑到 $i$ 时，设有 $x$ 对相邻的 $i + 1$，当前我们要填入 $y$ 个数。发现有 $x$ 个 $i$ 要填在 $i + 1$ 之间，剩下的 $y-x$ 个 $i$ 可以与已经填的 $x$ 个 $i$ 构成 $y-x$ 对相邻的 $i$。至此，我们成功想出了一个构造方案，而且将我们构造的良好的序列还原回去可以得到至少能构造出一个良好序列的优秀序列。
但是还有 $k$ 的限制，我们不妨再设一维状态 $l$ 表示当前良好序列所对应的优秀序列能排列出良好序列的方案数。
设 $f_{i,j,k,l}$ 表示考虑到数 $i$，已经填了 $j$ 个数，还剩 $k$ 对要填的数，方案数为 $l$。则可以推出转移方程：
$$\Large f_{i,j+y,y-x,l \times C_{y-1}^{x-1}} = \sum f_{i+1,j,x,l}$$
~~剩下的细节你自己想吧~~ 详见代码。
Code
```cpp
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 105;
const int M = 1e9 + 7;
int n, m, k, cs;
ll f[2][N][N][N];
int c[N][N];
int main() {
ios::sync_with_stdio(0);
cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> m >> k;
c[0][0] = 1;
for(int i = 1; i < N; ++i) {
for(int j = 0; j <= i; ++j)
if(!j) c[i][j] = c[i - 1][j];
else c[i][j] = min(k + 1, c[i - 1][j] + c[i - 1][j - 1]);
}
ll ans = 0; n++;
f[cs][0][1][1] = 1;
for(int i = 0; i <= m; ++i) {
cs ^= 1;
if(i) {
ll sum = 0;
for(int t = 2; t <= n; ++t) {
for(int l = 1; l <= k; ++l)
sum = (sum + f[cs ^ 1][t][0][l]) % M;
}
ans = (ans + (m - i + 1) * sum % M) % M;
}
memset(f[cs], 0, sizeof f[cs]);
for(int j = 0; j <= n; ++j) {
for(int x = 1; x <= n; ++x)
for(int l = 1; l <= k; ++l)
if(f[cs ^ 1][j][x][l])
for(int y = x; y + j <= n; ++y)
(f[cs][j + y][y - x][min(k + 1, l * c[y - 1][x - 1])] += f[cs ^ 1][j][x][l]) %= M;
}
}
cout << ans;
return 0;
}
```