#include <bits/stdc++.h>
using namespace std;
namespace fastIO {
bool IOerror = 0;
inline char nc() {
  static char buf[100000], *p1 = buf + 100000, *pend = buf + 100000;
  if (p1 == pend) {
    p1 = buf;
    pend = buf + fread(buf, 1, 100000, stdin);
    if (pend == p1) {
      IOerror = 1;
      return -1;
    }
  }
  return *p1++;
}
inline bool blank(char ch) {
  return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
}
inline long long read() {
  long long ans = 0, f = 1;
  char c = nc();
  while (c > '9' || c < '0') {
    if (c == '-') f = -1;
    c = nc();
  }
  while (c >= '0' && c <= '9') {
    ans = ans * 10 + c - '0';
    c = nc();
  }
  return ans * f;
}
};  // namespace fastIO
using namespace fastIO;
inline void write(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x / 10) write(x / 10);
  putchar((char)(x % 10) + '0');
}
template <typename T>
inline T Abs(T a) {
  return a > 0 ? a : -a;
};
template <typename T, typename TT>
inline T Min(T a, TT b) {
  return a < b ? a : b;
}
template <typename T, typename TT>
inline T Max(T a, TT b) {
  return a < b ? b : a;
}
const long long N = 2005, K = 105, mod = 998244353;
long long n, k, l[N], r[N], dp[2][N][N], sm[2][N][N], jc[N], inv[N];
inline long long q_pow(long long a, long long b) {
  long long c = 1;
  while (b) {
    if (b & 1) c = a * c % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return c;
}
inline void init(long long x) {
  jc[0] = 1;
  for (long long i = 1; i <= x; ++i) jc[i] = jc[i - 1] * i % mod;
  inv[x] = q_pow(jc[x], mod - 2);
  for (long long i = x - 1; i >= 0; --i) inv[i] = inv[i + 1] * (i + 1) % mod;
}
signed main() {
  init(2000);
  n = read();
  k = read();
  for (long long i = 1; i <= n; ++i) {
    long long x = read();
    l[i] = Max(0, x - k);
    r[i] = Min(i, x + k);
  }
  dp[0][0][0] = 1;
  sm[0][0][0] = 1;
  for (long long I = 1, i = 1; I <= n; ++I, i ^= 1) {
    for (long long j = 0; j <= I; ++j)
      for (long long k = l[I]; k <= r[I] && k <= j; ++k) {
        dp[i][j][k] = (dp[i][j][k] + dp[i ^ 1][j][k] * j % mod) % mod;
        if (j) dp[i][j][k] = (dp[i][j][k] + dp[i ^ 1][j - 1][k]) % mod;
        if (j && k)
          dp[i][j][k] = (dp[i][j][k] + sm[i ^ 1][j - 1][Min(k - 1, r[I - 1])] *
                                           inv[j - k] % mod) %
                        mod;
        sm[i][j][k] = dp[i][j][k] * jc[j - k] % mod;
        if (k) sm[i][j][k] = (sm[i][j][k] + sm[i][j][k - 1]) % mod;
      }
    for (long long j = 0; j <= I - 1; ++j)
      for (long long k = l[I - 1]; k <= r[I - 1] && k <= j; ++k)
        dp[i ^ 1][j][k] = sm[i ^ 1][j][k] = 0;
  }
  long long ans = 0;
  for (long long i = 0; i <= n; ++i)
    for (long long j = l[n]; j <= r[n] && j <= i; ++j)
      ans = (ans + dp[n & 1][i][j] * jc[n - j] % mod * inv[n - i] % mod) % mod;
  write(ans);
  return 0;
}

### Prompt

Develop a solution in CPP to the problem described below:

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;
namespace fastIO {
bool IOerror = 0;
inline char nc() {
  static char buf[100000], *p1 = buf + 100000, *pend = buf + 100000;
  if (p1 == pend) {
    p1 = buf;
    pend = buf + fread(buf, 1, 100000, stdin);
    if (pend == p1) {
      IOerror = 1;
      return -1;
    }
  }
  return *p1++;
}
inline bool blank(char ch) {
  return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
}
inline long long read() {
  long long ans = 0, f = 1;
  char c = nc();
  while (c > '9' || c < '0') {
    if (c == '-') f = -1;
    c = nc();
  }
  while (c >= '0' && c <= '9') {
    ans = ans * 10 + c - '0';
    c = nc();
  }
  return ans * f;
}
};  // namespace fastIO
using namespace fastIO;
inline void write(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x / 10) write(x / 10);
  putchar((char)(x % 10) + '0');
}
template <typename T>
inline T Abs(T a) {
  return a > 0 ? a : -a;
};
template <typename T, typename TT>
inline T Min(T a, TT b) {
  return a < b ? a : b;
}
template <typename T, typename TT>
inline T Max(T a, TT b) {
  return a < b ? b : a;
}
const long long N = 2005, K = 105, mod = 998244353;
long long n, k, l[N], r[N], dp[2][N][N], sm[2][N][N], jc[N], inv[N];
inline long long q_pow(long long a, long long b) {
  long long c = 1;
  while (b) {
    if (b & 1) c = a * c % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return c;
}
inline void init(long long x) {
  jc[0] = 1;
  for (long long i = 1; i <= x; ++i) jc[i] = jc[i - 1] * i % mod;
  inv[x] = q_pow(jc[x], mod - 2);
  for (long long i = x - 1; i >= 0; --i) inv[i] = inv[i + 1] * (i + 1) % mod;
}
signed main() {
  init(2000);
  n = read();
  k = read();
  for (long long i = 1; i <= n; ++i) {
    long long x = read();
    l[i] = Max(0, x - k);
    r[i] = Min(i, x + k);
  }
  dp[0][0][0] = 1;
  sm[0][0][0] = 1;
  for (long long I = 1, i = 1; I <= n; ++I, i ^= 1) {
    for (long long j = 0; j <= I; ++j)
      for (long long k = l[I]; k <= r[I] && k <= j; ++k) {
        dp[i][j][k] = (dp[i][j][k] + dp[i ^ 1][j][k] * j % mod) % mod;
        if (j) dp[i][j][k] = (dp[i][j][k] + dp[i ^ 1][j - 1][k]) % mod;
        if (j && k)
          dp[i][j][k] = (dp[i][j][k] + sm[i ^ 1][j - 1][Min(k - 1, r[I - 1])] *
                                           inv[j - k] % mod) %
                        mod;
        sm[i][j][k] = dp[i][j][k] * jc[j - k] % mod;
        if (k) sm[i][j][k] = (sm[i][j][k] + sm[i][j][k - 1]) % mod;
      }
    for (long long j = 0; j <= I - 1; ++j)
      for (long long k = l[I - 1]; k <= r[I - 1] && k <= j; ++k)
        dp[i ^ 1][j][k] = sm[i ^ 1][j][k] = 0;
  }
  long long ans = 0;
  for (long long i = 0; i <= n; ++i)
    for (long long j = l[n]; j <= r[n] && j <= i; ++j)
      ans = (ans + dp[n & 1][i][j] * jc[n - j] % mod * inv[n - i] % mod) % mod;
  write(ans);
  return 0;
}

```