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>
  #pragma GCC optimize("Ofast")
  using namespace std;
  using ll = long long;
  using ld = long double;
  const ll mod = 998244353;
  ll gcd(ll a, ll b) {
    a = abs(a);
    b = abs(b);
    if (a == 0 or b == 0) return a + b;
    return gcd(b, a % b);
  }
  ll sum(ll a, ll b) {
    a += b;
    a %= mod;
    return a;
  }
  ll sub(ll a, ll b) {
    a += mod - b;
    a %= mod;
    return a;
  }
  inline ll mul(ll a, ll b) {
    if (a * b < mod) return a * b;
    return a * b % mod;
  }
  inline ll pew(ll a, ll b) {
    ll res = 1;
    while (b) {
      if (b & 1) res = mul(res, a);
      a = mul(a, a);
      b /= 2;
    }
    return res;
  }
  int main() {
    ios_base::sync_with_stdio(false);
    ll n, k;
    cin >> n >> k;
    vector<ll> b(n + 1);
    for (ll i = 0; i < n; i++) {
      cin >> b[i + 1];
    }
    b[0] = 0;
    vector<vector<ll>> dp(2 * k + 1, vector<ll>(n + 1));
    vector<vector<ll>> dp2(2 * k + 1, vector<ll>(n + 1));
    dp[k][0] = 1;
    for (ll i = 1; i <= n; i++) {
      for (ll j = 0; j <= 2 * k; j++) {
        for (ll d = 0; d <= n; d++) dp2[j][d] = 0;
      }
      for (ll j = max(0LL, k - b[i - 1]); j <= 2 * k; j++) {
        ll j2 = j + b[i - 1] - b[i] + 1;
        ll x = j + b[i - 1] - k;
        if (x < 0 or x > n) continue;
        if (j2 > 2 * k) continue;
        for (ll d = max(0LL, -j2); d < i; d++) {
          if (j2 < 0)
            dp2[0][d + j2] = (dp2[0][d + j2] + dp[j][d]) % mod;
          else
            dp2[j2][d] = (dp2[j2][d] + dp[j][d]) % mod;
        }
      }
      for (ll j = 0; j < 2 * k; j++) {
        for (ll d = 1; d <= i; d++) {
          dp2[j + 1][d - 1] = (dp2[j + 1][d - 1] + dp2[j][d]) % mod;
        }
      }
      for (ll j = max(0LL, k - b[i - 1]); j <= 2 * k; j++) {
        ll j2 = j + b[i - 1] - b[i];
        ll x = j + b[i - 1] - k;
        if (x < 0 or x > n) continue;
        if (j2 >= 0 and j2 <= 2 * k) {
          for (ll d = 0; d < i; d++) {
            dp2[j2][d] = (dp2[j2][d] + dp[j][d] * (d + x)) % mod;
            dp2[j2][d + 1] = (dp2[j2][d + 1] + dp[j][d] * (d + 1)) % mod;
          }
        }
      }
      swap(dp, dp2);
    }
    vector<vector<ll>> c(n + 2);
    for (ll i = 0; i <= n + 1; i++) {
      c[i].resize(i + 1);
      c[i][0] = c[i][i] = 1;
      for (ll j = 1; j < i; j++) c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
    }
    ll A = 0;
    for (ll j = 0; j <= 2 * k; j++) {
      ll x = b[n] + j - k;
      if (x < 0 or x > n) continue;
      ll Q = 1;
      for (ll d = 0; d <= n - x; d++) {
        A = (A + dp[j][d] * c[n - x][d]) % mod;
      }
    }
    cout << A << endl;
  }
  