dp を累積和で高速化する．
\(dp_{i,j} := [0,i)\) まで，last \(j\) のときの答え
とする．
今を\(y \in M\)，直前を \(x \in M\) とすると， 遷移は
\(dp_{i+1, y} += \sum_{x \in [l,r) } dp_{i,x} \)
となるので，累積和で高速化できる．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n, m, k ;
cin >> n >> m >> k;
if(k == 0){
cout << mint(m).pow(n).val() << endl;
return 0;
}
rep(j,m) dp[j] = 1;
rep(i,n-1){
swap(dp, old);
rep(j,m) s[j+1] = s[j] + old[j];
auto sum = [&](ll l, ll r) -> mint {
if(l > r) return mint(0);
return -s[l] + s[r];
};
rep(y,m){
dp[y] += sum(0, min(m, y-k+1)) + sum(max(y+k,0LL), m);
}
}
mint ans;
rep(j,m) ans += dp[j];
cout << ans.val() << endl;
return 0;
}
