#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 2010;
const long long MAXK = 55;
const long long INF = 2e9;
const double eps = 1e-6;
const double PI = acos(-1);
const long long mod = 998244353;
long long n, k, Ans;
long long b[MAXN], L[MAXN], R[MAXN];
long long fac[MAXN], ifac[MAXN], Inv[MAXN];
long long dp[2][MAXK << 1][MAXN];
long long coef[2][MAXK << 1][MAXN];
template <typename T>
inline bool read(T &a) {
  a = 0;
  char c = getchar();
  long long f = 1;
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    a = a * 10 + (c ^ 48);
    c = getchar();
  }
  return a *= f, true;
}
template <typename A, typename... B>
inline bool read(A &x, B &...y) {
  return read(x) && read(y...);
}
void pushup(long long i) {
  for (long long j = max(0ll, L[i]); j <= min(i, R[i]); ++j)
    for (long long c = 0; c <= i; ++c) {
      if (j > L[i] && coef[(i)&1][(j - 1) - b[i] + k][c + 1])
        (coef[(i)&1][(j)-b[i] + k][c] +=
         coef[(i)&1][(j - 1) - b[i] + k][c + 1] * (c + 1)) %= mod;
      (dp[(i)&1][(j)-b[i] + k][c] += coef[(i)&1][(j)-b[i] + k][c]) %= mod;
    }
}
signed main() {
  read(n), read(k);
  Inv[1] = fac[0] = ifac[0] = 1;
  for (long long i = 1; i <= n; ++i) read(b[i]);
  for (long long i = 0; i <= n; ++i) L[i] = b[i] - k, R[i] = b[i] + k;
  for (long long i = 2; i < MAXN; ++i)
    Inv[i] = Inv[mod % i] * (mod - mod / i) % mod;
  for (long long i = 1; i < MAXN; ++i) {
    fac[i] = fac[i - 1] * i % mod;
    ifac[i] = ifac[i - 1] * Inv[i] % mod;
  }
  dp[(0) & 1][(0) - b[0] + k][0] = 1;
  for (long long i = 0; i < n; ++i) {
    memset(dp[(i + 1) & 1], 0, sizeof dp[(i + 1) & 1]);
    memset(coef[(i + 1) & 1], 0, sizeof coef[(i + 1) & 1]);
    for (long long j = max(0ll, L[i]); j <= min(i, R[i]); ++j) {
      for (long long c = 0, p; c <= i; ++c) {
        if (!dp[(i)&1][(j)-b[i] + k][c]) continue;
        if (L[i + 1] <= j && j <= R[i + 1]) {
          (dp[(i + 1) & 1][(j)-b[i + 1] + k][c] +=
           dp[(i)&1][(j)-b[i] + k][c] * (j + c)) %= mod;
          (dp[(i + 1) & 1][(j)-b[i + 1] + k][c + 1] +=
           dp[(i)&1][(j)-b[i] + k][c]) %= mod;
        }
        if (j <= R[i + 1]) {
          p = max(j + 1, L[i + 1]) - j;
          if (p - 1 <= c)
            (coef[(i + 1) & 1][(j + p) - b[i + 1] + k][c - p + 1] +=
             dp[(i)&1][(j)-b[i] + k][c] * fac[c] % mod * ifac[c - p + 1]) %=
                mod;
        }
      }
    }
    pushup(i + 1);
  }
  for (long long j = max(0ll, L[n]); j <= min(n, R[n]); ++j)
    for (long long c = 0; c <= n; ++c)
      if (c <= n - j && dp[(n)&1][(j)-b[n] + k][c])
        (Ans += dp[(n)&1][(j)-b[n] + k][c] * fac[n - j] % mod *
                ifac[n - j - c]) %= mod;
  printf("%lld\n", Ans);
  return 0;
}

### Prompt

Create a solution in Cpp for the following problem:

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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 2010;
const long long MAXK = 55;
const long long INF = 2e9;
const double eps = 1e-6;
const double PI = acos(-1);
const long long mod = 998244353;
long long n, k, Ans;
long long b[MAXN], L[MAXN], R[MAXN];
long long fac[MAXN], ifac[MAXN], Inv[MAXN];
long long dp[2][MAXK << 1][MAXN];
long long coef[2][MAXK << 1][MAXN];
template <typename T>
inline bool read(T &a) {
  a = 0;
  char c = getchar();
  long long f = 1;
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    a = a * 10 + (c ^ 48);
    c = getchar();
  }
  return a *= f, true;
}
template <typename A, typename... B>
inline bool read(A &x, B &...y) {
  return read(x) && read(y...);
}
void pushup(long long i) {
  for (long long j = max(0ll, L[i]); j <= min(i, R[i]); ++j)
    for (long long c = 0; c <= i; ++c) {
      if (j > L[i] && coef[(i)&1][(j - 1) - b[i] + k][c + 1])
        (coef[(i)&1][(j)-b[i] + k][c] +=
         coef[(i)&1][(j - 1) - b[i] + k][c + 1] * (c + 1)) %= mod;
      (dp[(i)&1][(j)-b[i] + k][c] += coef[(i)&1][(j)-b[i] + k][c]) %= mod;
    }
}
signed main() {
  read(n), read(k);
  Inv[1] = fac[0] = ifac[0] = 1;
  for (long long i = 1; i <= n; ++i) read(b[i]);
  for (long long i = 0; i <= n; ++i) L[i] = b[i] - k, R[i] = b[i] + k;
  for (long long i = 2; i < MAXN; ++i)
    Inv[i] = Inv[mod % i] * (mod - mod / i) % mod;
  for (long long i = 1; i < MAXN; ++i) {
    fac[i] = fac[i - 1] * i % mod;
    ifac[i] = ifac[i - 1] * Inv[i] % mod;
  }
  dp[(0) & 1][(0) - b[0] + k][0] = 1;
  for (long long i = 0; i < n; ++i) {
    memset(dp[(i + 1) & 1], 0, sizeof dp[(i + 1) & 1]);
    memset(coef[(i + 1) & 1], 0, sizeof coef[(i + 1) & 1]);
    for (long long j = max(0ll, L[i]); j <= min(i, R[i]); ++j) {
      for (long long c = 0, p; c <= i; ++c) {
        if (!dp[(i)&1][(j)-b[i] + k][c]) continue;
        if (L[i + 1] <= j && j <= R[i + 1]) {
          (dp[(i + 1) & 1][(j)-b[i + 1] + k][c] +=
           dp[(i)&1][(j)-b[i] + k][c] * (j + c)) %= mod;
          (dp[(i + 1) & 1][(j)-b[i + 1] + k][c + 1] +=
           dp[(i)&1][(j)-b[i] + k][c]) %= mod;
        }
        if (j <= R[i + 1]) {
          p = max(j + 1, L[i + 1]) - j;
          if (p - 1 <= c)
            (coef[(i + 1) & 1][(j + p) - b[i + 1] + k][c - p + 1] +=
             dp[(i)&1][(j)-b[i] + k][c] * fac[c] % mod * ifac[c - p + 1]) %=
                mod;
        }
      }
    }
    pushup(i + 1);
  }
  for (long long j = max(0ll, L[n]); j <= min(n, R[n]); ++j)
    for (long long c = 0; c <= n; ++c)
      if (c <= n - j && dp[(n)&1][(j)-b[n] + k][c])
        (Ans += dp[(n)&1][(j)-b[n] + k][c] * fac[n - j] % mod *
                ifac[n - j - c]) %= mod;
  printf("%lld\n", Ans);
  return 0;
}

```