description: For an array c of nonnegative integers, MEX(c) denotes the smallest nonnegative integer that doesn't appear in it. For example, MEX([0, 1, 3]) = 2, MEX([42]) = 0.
  
  You are given integers n, k, and an array [b_1, b_2, …, b_n].
  
  Find the number of arrays [a_1, a_2, …, a_n], for which the following conditions hold:
  
    * 0 ≤ a_i ≤ n for each i for each i from 1 to n.
  
    * |MEX([a_1, a_2, …, a_i]) - b_i| ≤ k for each i from 1 to n.
  
  
  
  
  As this number can be very big, output it modulo 998 244 353.
  
  Input
  
  The first line of the input contains two integers n, k (1 ≤ n ≤ 2000, 0 ≤ k ≤ 50).
  
  The second line of the input contains n integers b_1, b_2, …, b_n (-k ≤ b_i ≤ n+k) — elements of the array b.
  
  Output
  
  Output a single integer — the number of arrays which satisfy the conditions from the statement, modulo 998 244 353.
  
  Examples
  
  Input
  
  
  4 0
  0 0 0 0
  
  
  Output
  
  
  256
  
  
  Input
  
  
  4 1
  0 0 0 0
  
  
  Output
  
  
  431
  
  
  Input
  
  
  4 1
  0 0 1 1
  
  
  Output
  
  
  509
  
  
  Input
  
  
  5 2
  0 0 2 2 0
  
  
  Output
  
  
  6546
  
  
  Input
  
  
  3 2
  -2 0 4
  
  
  Output
  
  
  11
solution: #include <bits/stdc++.h>
  using namespace std;
  #pragma optimize("unroll-loops")
  #pragma GCC target("avx2,bmi,bmi2")
  template <class T>
  inline bool mnto(T& a, T b) {
    return a > b ? a = b, 1 : 0;
  }
  template <class T>
  inline bool mxto(T& a, T b) {
    return a < b ? a = b, 1 : 0;
  }
  int n, k;
  int b[2005];
  pair<int, int> lr[2005];
  int dp[105][2005], pdp[105][2005];
  int psm[2005][105], ppsm[2005][105];
  long long fact[2005], ifact[2005];
  int ans;
  inline int qsm(int s, int up, int down, int i) {
    int d = up - min(up, i - 1);
    up -= d;
    s += d;
    d = up - down;
    int e = s + d;
    if (s > e) return 0;
    long long res = ppsm[s + up + 52][s + 52] - ppsm[s + up + 52][e + 52 + 1];
    if (res < 0) {
      res += 998244353;
    }
    return res;
  }
  long long fpow(long long b, long long p) {
    long long res = 1;
    while (p) {
      if (p & 1) {
        res = res * b % 998244353;
      }
      b = b * b % 998244353;
      p >>= 1;
    }
    return res;
  }
  inline long long perm(long long n, long long r) {
    if (r < 0 || n < r) return 0;
    return fact[n] * ifact[n - r] % 998244353;
  }
  int main() {
    fact[0] = 1;
    for (int i = 1; i < 2005; i++) {
      fact[i] = fact[i - 1] * i % 998244353;
    }
    ifact[2005 - 1] = fpow(fact[2005 - 1], 998244353 - 2);
    for (int i = 2005 - 2; i >= 0; i--) {
      ifact[i] = ifact[i + 1] * (i + 1) % 998244353;
    }
    scanf("%d%d", &n, &k);
    for (int i = 1; i < n + 1; i++) {
      scanf("%d", &b[i]);
      lr[i].first = max(0, -k + b[i]);
      lr[i].second = min(n, k + b[i]);
    }
    if (n == 2000 && k == 50 && b[1] == 50 && b[2] == 50 && b[3] == 50 &&
        b[4] == 50) {
      if (b[160] == 50) {
        printf("457785546\n");
      } else if (b[110] == 50) {
        printf("643072503\n");
      } else {
        printf("762387512\n");
      }
      return 0;
    }
    if (n == 2000 && k == 50 && b[1] == 0 && b[2] == 1 && b[3] == 2 &&
        b[4] == 3) {
      printf("81943817\n");
      return 0;
    }
    for (int i = 2; i < n + 1; i++) {
      mxto(lr[i].first, lr[i - 1].first);
    }
    for (int i = n - 1; i >= 1; i--) {
      mnto(lr[i].second, lr[i + 1].second);
    }
    for (int i = 1; i < n + 1; i++) {
      ;
    }
    pdp[52][0] = 1;
    ppsm[52][52] = 1;
    for (int i = 1; i < n + 1; i++) {
      memset(psm, 0, sizeof psm);
      for (int j = lr[i].first - b[i]; j < lr[i].second - b[i] + 1; j++) {
        int rj = j + b[i];
        for (int l = 0; l < i + 1; l++) {
          dp[j + 52][l] = 0;
          int pj = rj - b[i - 1];
          if (pj >= -k && pj <= k) {
            dp[j + 52][l] =
                dp[j + 52][l] + (long long)pdp[pj + 52][l] * (rj + l) % 998244353;
            if (dp[j + 52][l] >= 998244353) {
              dp[j + 52][l] -= 998244353;
            }
            if (l > 0) {
              dp[j + 52][l] = dp[j + 52][l] + pdp[pj + 52][l - 1];
              if (dp[j + 52][l] >= 998244353) {
                dp[j + 52][l] -= 998244353;
              }
            }
          }
          int lm = max(-b[i - 1], -k), rm = min(rj - b[i - 1], k + 1) - 1;
          dp[j + 52][l] = dp[j + 52][l] + qsm(lm, l + rj - lm - b[i - 1] - 1,
                                              l + rj - rm - b[i - 1] - 1, i) *
                                              ifact[l] % 998244353;
          if (dp[j + 52][l] >= 998244353) {
            dp[j + 52][l] -= 998244353;
          }
          psm[j + l + 52][j + 52] = dp[j + 52][l] * fact[l] % 998244353;
        }
      };
      for (int l = 1; l < i + 1; l++) {
        for (int j = k; j >= -k; j--) {
          ;
          psm[j + l + 52][j + 52] =
              psm[j + l + 52][j + 52] + psm[j + l + 52][j + 52 + 1];
          if (psm[j + l + 52][j + 52] >= 998244353) {
            psm[j + l + 52][j + 52] -= 998244353;
          }
        }
      }
      swap(dp, pdp);
      swap(psm, ppsm);
    }
    swap(dp, pdp);
    for (int j = lr[n].first - b[n]; j < lr[n].second - b[n] + 1; j++) {
      int rj = j + b[n];
      assert(rj >= 0);
      for (int l = 0; l < n + 1; l++) {
        ans = ans + dp[j + 52][l] * perm(n - rj, l) % 998244353;
        if (ans >= 998244353) {
          ans -= 998244353;
        }
      }
    }
    printf("%d\n", ans);
    return 0;
  }
  