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;
  const int Mod = 1000000007LL;
  const int N = 2e3 + 10;
  const int K = 105;
  const int Log = 30;
  const long long Inf = 2242545357980376863LL;
  namespace ModularInt {
  template <typename T>
  T inverse(T a, T pr) {
    T u = 1, v = 0;
    while (a != 0) {
      T dv = pr / a;
      pr -= dv * a;
      v -= dv * u;
      swap(a, pr);
      swap(u, v);
    }
    assert(pr == 1);
    return v;
  }
  template <typename ModT>
  class Mint {
   public:
    using T = typename decay<decltype(ModT::value)>::type;
    T val;
    Mint() : val() {}
    template <typename Q>
    Mint(const Q& x) {
      val = normalize(x);
    }
    Mint(const Mint& x) { val = x.val; }
    template <typename U>
    explicit operator U() const {
      return static_cast<U>(val);
    }
    constexpr static T _Mod() { return ModT::value; }
    friend Mint inverse(Mint x) { return inverse(x.val, _Mod()); }
    template <typename Q>
    static T normalize(const Q& x) {
      T val;
      if (-_Mod() <= x && x < _Mod())
        val = x;
      else
        val = x % _Mod();
      if (val < 0) val += _Mod();
      return val;
    }
    template <typename Q>
    Mint& operator=(const Q& x) {
      val = normalize(x);
      return *this;
    }
    Mint& operator+=(const Mint& other) {
      if (_Mod() <= (val += other.val)) val -= _Mod();
      return *this;
    }
    Mint& operator-=(const Mint& other) {
      if ((val -= other.val) < 0) val += _Mod();
      return *this;
    }
    template <typename Q>
    Mint& operator+=(const Q& other) {
      return (*this) += Mint(other);
    };
    template <typename Q>
    Mint& operator-=(const Q& other) {
      return (*this) -= Mint(other);
    };
    Mint& operator++() { return (*this) += 1; }
    Mint& operator--() { return (*this) -= 1; }
    Mint operator++(int) {
      Mint res(*this);
      (*this) += 1;
      return res;
    }
    Mint operator--(int) {
      Mint res(*this);
      (*this) -= 1;
      return res;
    }
    Mint operator+() {
      Mint res(val);
      return res;
    }
    Mint operator-() {
      Mint res(-val);
      return res;
    }
    Mint& operator*=(const Mint& other) {
      val = (1ll * val * other.val) % _Mod();
      return *this;
    }
    Mint& operator/=(const Mint& other) { return (*this) *= inverse(other); }
    template <typename Q>
    Mint& operator*=(const Q& other) {
      return (*this) *= Mint(other);
    }
    template <typename Q>
    Mint& operator/=(const Q& other) {
      return (*this) /= Mint(other);
    }
  };
  template <typename T>
  Mint<T> operator+(const Mint<T>& lhs, const Mint<T>& rhs) {
    return Mint<T>(lhs) += rhs;
  }
  template <typename T, typename Q>
  Mint<T> operator+(const Q& lhs, const Mint<T>& rhs) {
    return Mint<T>(lhs) += rhs;
  }
  template <typename T, typename Q>
  Mint<T> operator+(const Mint<T>& lhs, const Q& rhs) {
    return Mint<T>(lhs) += rhs;
  }
  template <typename T>
  Mint<T> operator-(const Mint<T>& lhs, const Mint<T>& rhs) {
    return Mint<T>(lhs) -= rhs;
  }
  template <typename T, typename Q>
  Mint<T> operator-(const Q& lhs, const Mint<T>& rhs) {
    return Mint<T>(lhs) -= rhs;
  }
  template <typename T, typename Q>
  Mint<T> operator-(const Mint<T>& lhs, const Q& rhs) {
    return Mint<T>(lhs) -= rhs;
  }
  template <typename T>
  Mint<T> operator*(const Mint<T>& lhs, const Mint<T>& rhs) {
    return Mint<T>(lhs) *= rhs;
  }
  template <typename T, typename Q>
  Mint<T> operator*(const Q& lhs, const Mint<T>& rhs) {
    return Mint<T>(lhs) *= rhs;
  }
  template <typename T, typename Q>
  Mint<T> operator*(const Mint<T>& lhs, const Q& rhs) {
    return Mint<T>(lhs) *= rhs;
  }
  template <typename T>
  Mint<T> operator/(const Mint<T>& lhs, const Mint<T>& rhs) {
    return Mint<T>(lhs) /= rhs;
  }
  template <typename T, typename Q>
  Mint<T> operator/(const Q& lhs, const Mint<T>& rhs) {
    return Mint<T>(lhs) /= rhs;
  }
  template <typename T, typename Q>
  Mint<T> operator/(const Mint<T>& lhs, const Q& rhs) {
    return Mint<T>(lhs) /= rhs;
  }
  template <typename T>
  bool operator==(const Mint<T>& lhs, const Mint<T>& rhs) {
    return lhs.val == rhs.val;
  }
  template <typename T, typename Q>
  bool operator==(const Q& lhs, const Mint<T>& rhs) {
    return Mint<T>(lhs) == rhs;
  }
  template <typename T, typename Q>
  bool operator==(const Mint<T>& lhs, const Q& rhs) {
    return lhs == Mint<T>(rhs);
  }
  template <typename T>
  bool operator!=(const Mint<T>& lhs, const Mint<T>& rhs) {
    return !(lhs == rhs);
  }
  template <typename T, typename Q>
  bool operator!=(const Q& lhs, const Mint<T>& rhs) {
    return !(lhs == rhs);
  }
  template <typename T, typename Q>
  bool operator!=(const Mint<T>& lhs, const Q& rhs) {
    return !(lhs == rhs);
  }
  template <typename T, typename IO>
  IO& operator<<(IO& ostream, const Mint<T>& _x) {
    return ostream << _x.val;
  }
  template <typename T, typename IO>
  IO& operator>>(IO& istream, Mint<T>& _x) {
    return istream >> _x.val;
  }
  template <typename T, typename Q>
  Mint<T> bin_pow(const Mint<T>& base, Q power) {
    assert(0 <= power);
    Mint<T> res = 1, pw = base;
    for (Q j = 1; j <= power; j <<= 1, pw *= pw)
      if (j & power) res *= pw;
    return res;
  }
  constexpr int MintMod = 998244353;
  using mi = Mint<integral_constant<decay<decltype(MintMod)>::type, MintMod>>;
  };  // namespace ModularInt
  using namespace ModularInt;
  int k;
  mi dp[2][N][K], tmp[N][K];
  int b[N];
  int Get(int i, int mx) {
    int res = mx - b[i] + 50;
    return res;
  }
  int Undo(int i, int mx) { return mx - 50 + b[i]; }
  mi f[N], iv[N];
  mi nCr(int n, int r) {
    if (r < 0 || n < 0 || n < r) return 0;
    return f[n] * iv[r] * iv[n - r];
  }
  int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    f[0] = 1;
    for (int i = 1; i < N; i++) f[i] = i * f[i - 1];
    for (int i = 0; i < N; i++) iv[i] = inverse(f[i]);
    int n;
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> b[i];
    if (abs(b[0]) <= k) dp[0][1][Get(0, 0)] = 1;
    if (abs(b[0] - 1) <= k) dp[0][1][Get(0, 1)] = 1;
    int nw, nx;
    for (int i = 1; i < n; i++) {
      for (int cnt = 1; cnt <= i + 1; cnt++) {
        for (int mex = 0; mex < K - 1; mex++) {
          if (dp[0][cnt][mex] == 0) continue;
          nw = Undo(i - 1, mex);
          if (abs(nw - b[i - 1]) > k) continue;
          nx = Get(i, nw);
          if (abs(nw - b[i]) <= k) {
            dp[1][cnt][nx] += cnt * dp[0][cnt][mex];
            dp[1][cnt + 1][nx] += dp[0][cnt][mex];
          }
          int delta = 1;
          if (nw + delta > b[i] + k) continue;
          if (nw + delta < b[i] - k) delta = b[i] - k - nw;
          int st = cnt - nw;
          mi z = nCr(st, delta - 1) * f[delta - 1];
          tmp[cnt + 1][Get(i, nw + delta)] += dp[0][cnt][mex] * z;
        }
      }
      for (int cnt = 1; cnt <= i + 1; cnt++) {
        for (int mex = 0; mex < K - 1; mex++) {
          if (tmp[cnt][mex] == 0) continue;
          nw = Undo(i, mex);
          if (abs(nw - b[i]) > k) continue;
          if (abs((nw + 1) - b[i]) > k) continue;
          nx = Get(i, nw);
          tmp[cnt][nx + 1] += (cnt - nw) * tmp[cnt][mex];
        }
      }
      for (int cnt = 1; cnt <= i + 1; cnt++) {
        for (int mex = 0; mex < K - 1; mex++) {
          nw = Undo(i, mex);
          if (abs(nw - b[i]) > k) {
            dp[1][cnt][mex] = 0;
            dp[0][cnt][mex] = 0;
            tmp[cnt][mex] = 0;
            continue;
          }
          dp[0][cnt][mex] = tmp[cnt][mex] + dp[1][cnt][mex];
          dp[1][cnt][mex] = 0;
          tmp[cnt][mex] = 0;
        }
      }
    }
    mi ans = 0;
    for (int cnt = 1; cnt <= n; cnt++) {
      for (int mex = 0; mex < K - 1; mex++) {
        nw = Undo(n - 1, mex);
        if (dp[0][cnt][mex] == 0) continue;
        if (abs(nw - b[n - 1]) > k) continue;
        if (cnt >= nw) {
          int tot = n - nw;
          int rem = cnt - nw;
          ans += f[rem] * dp[0][cnt][mex] * nCr(tot, rem);
        }
      }
    }
    cout << ans << '\n';
    return 0;
  }
  