本文把题面中的 $k$ 记为 $m$。

试图继承 Easy Version 的做法，但发现这样的状态设计本身就有问题。
由于要记录 $i,a_{i-1},a_i$，转移一定不可能低于 $O(nk^2)$，所以需要考虑别的做法。

经验丰富的选手一眼就看出可以容斥，所以显然我并不是经验丰富的选手。
容斥什么呢？再观察一下不合法的情况。

如果两个相邻位置 $a_{i-1},a_i$ 都不满足条件，则有 $a_{i-2}+a_i \lt a_{i-1}, a_{i-1}+a_{i+1} \lt a_i$。
把前者代入后者，得到 $a_i + a_{i-2} \lt 2$，这看上去就很对，所以矛盾了。

后面怎么做呢？在容斥过程中把每个方案出现的第一次不合法状态减掉即可。
设 $dp_{i,j}$ 表示前 $i$ 个，$a_i = j$ 的方案数。
则有转移方程：

$$dp_{i,j} = \sum\limits_{k} dp_{i-1,k} - \sum\limits_{k=0}^{m-j-1} dp_{i-2,k} \times (m-j-k)$$

解释一下意义。
先从 $dp_{i-1}$ 继承所有状态，但此时 $a_i$ 有部分情况是不合法的。
所以需要减去不合法的状态，考虑枚举 $k=a_{i-2}$。由于不合法的位置一定不相邻，所以不用管 $a_{i-1}$。
令 $a_{i-1} = x$。由于要保证不合法，所以 $a_{i-2}+a_i+1 \leq a_{i-1}$。
由于 $a_{i-2}=k,a_i=j,a_{i-1}=x$，且 $x \leq m$（定义），有：$k+j+1 \leq x \leq m$，即 $k+j+1 \leq m$。
移项，得 $k$ 的取值范围为 $0 \leq k \leq m-j-1$。
而后面的 $m-j-k$ 表示 $a_{i-1}$ 的取值个数。

这个式子的复杂度仍然是 $O(nk^2)$，需要优化。
发现 $k$ 的取值范围仍然是一段前缀，所以可以前缀和优化。
但是这好像不是很好前缀和？其实是可以的，在转移 $dp_i$ 的时候倒着枚举 $k$，把 $m-j-k$ 这个系数拆开成若干个前缀和即可。

小心越界。

#include <bits/stdc++.h>
using namespace std;
const int N = 3015;
int T, n, m, mod;
int dp[N][N], sum[N][N];

void solve() {
    scanf("%d%d%d", &n, &m, &mod);
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= m; j++) dp[i][j] = sum[i][j] = 0;

    for (int i = 0; i <= m; i++) dp[0][i] = 1, sum[0][i] = i + 1;
    for (int i = 1; i <= n; i++) {
        int s = 0, all = sum[i - 1][m];
        for (int j = m; j >= 0; j--) {
            if (i == 1 && m - j - 1 >= 0) s++;
            else if (m - j - 1 >= 0) (s += sum[i - 2][m - j - 1]) %= mod;
            dp[i][j] = (all - s + mod) % mod;
        }
        sum[i][0] = dp[i][0];
        for (int j = 1; j <= m; j++) sum[i][j] = (sum[i][j - 1] + dp[i][j]) % mod;
    }
    printf("%d\n", dp[n][0]);
}

int main() {
    scanf("%d", &T);
    while (T--) solve();
    return 0;
}