【AtCoder Beginner Contest 253】E - Distance Sequence

int n, m, k;
int f[M], s[M];
void solve() {
  cin >> n >> m >> k;
  for (int i = 1; i <= m; i++) f[i] = 1; // i == 1;
  for (int i = 2; i <= n; i++) { // i > 1
    s[0] = 0;
    for (int j = 1; j <= m; j++)
      s[j] = (s[j - 1] + f[j]) % mod;
    int sum = s[m];
    for (int j = 1; j <= m; j++) {
      int l = max(1ll, j - k + 1);
      int r = min(m, j + k - 1);
      if(k > 0) f[j] = (sum - s[r] + s[l - 1] + mod) % mod;
      else f[j] = sum % mod;
    }
  }
  int res = 0;
  for (int i = 1; i <= m; i++) res = (res + f[i]) % mod;
  cout << res << endl;
}