题解

设序列为 $a_1, a_2, \ldots, a_K$，满足 $1 \le a_1 < a_2 < \cdots < a_K \le N$ 且相邻差值 $d_i = a_i - a_{i-1}$（$i \ge 2$）都不超过 $M$。对任意一组差值序列 $(d_2,\ldots,d_K)$，如果把它们的和记为 $S$，则 $a_K = a_1 + S$。由于 $S \le M (K-1) < N$，总能选出合法的 $a_1$，且 $a_1$ 可以取 $1 \sim N - S$ 的任意整数。因此对于固定的差值组合，合法序列的数量恰为 $N - S$。

所有差值相互独立，且每个 $d_i$ 有 $M$ 种取值，所以共有 $M^{K-1}$ 组差值序列。于是答案为

$$\sum (N - S) = N \cdot M^{K-1} - \sum S.$$

而 $\sum S$ 可以拆分：每个位置的差值在所有组合中出现 $M^{K-2}$ 次，差值取值之和为 $\frac{M(M+1)}{2}$，一共有 $K-1$ 个位置，因而

$$\sum S = (K-1) \cdot M^{K-2} \cdot \frac{M(M+1)}{2}. $$

把上述公式整理后再对模数 $P$ 取模即可。代码中使用快速幂求出 $M^{K-2}$，再套用推导出的闭式公式。

#include <iostream>

int main() {
    long long N, M, K, P;
    std::cin >> N >> K >> M >> P;
    
    long long s = 1, x = K - 2, n = M;
    for (; x; x /= 2, n = n * n % P)
        if (x & 1)
            s = s * n % P;
    
    std::cout << s * (N % P * M % P - (M + 1) * M / 2 % P * (K - 1) % P + P) % P << '\n';
    return 0;
}