#include <bits/stdc++.h>
using namespace std;
void read(int& x) {
  static char c;
  int f = 0;
  while (!isdigit(c = getchar()))
    if (c == '-') f = 1;
  x = c ^ 48;
  while (isdigit(c = getchar())) x = (x * 10) + (c ^ 48);
  if (f) x = -x;
}
void read(long long& x) {
  static char c;
  int f = 0;
  while (!isdigit(c = getchar()))
    if (c == '-') f = 1;
  x = c ^ 48;
  while (isdigit(c = getchar())) x = (x * 10) + (c ^ 48);
  if (f) x = -x;
}
void read(unsigned int& x) {
  static char c;
  while (!isdigit(c = getchar()))
    ;
  x = c ^ 48;
  while (isdigit(c = getchar())) x = (x * 10) + (c ^ 48);
}
void read(unsigned long long& x) {
  static char c;
  while (!isdigit(c = getchar()))
    ;
  x = c ^ 48;
  while (isdigit(c = getchar())) x = (x * 10) + (c ^ 48);
}
void chkmax(int& x, int y) {
  if (y > x) x = y;
}
void chkmin(int& x, int y) {
  if (y < x) x = y;
}
void chkmax(long long& x, long long y) {
  if (y > x) x = y;
}
void chkmin(long long& x, long long y) {
  if (y < x) x = y;
}
void chkmax(unsigned int& x, unsigned int y) {
  if (y > x) x = y;
}
void chkmin(unsigned int& x, unsigned int y) {
  if (y < x) x = y;
}
void chkmax(unsigned long long& x, unsigned long long y) {
  if (y > x) x = y;
}
void chkmin(unsigned long long& x, unsigned long long y) {
  if (y < x) x = y;
}
const int Mod = 998244353;
void Add(int& x, int y) { (x += y) >= Mod ? x -= Mod : x; }
void Del(int& x, int y) { (x -= y) < 0 ? x += Mod : x; }
int Pow(int a, int b) {
  int res = 1;
  while (b) {
    if (b & 1) res = 1ll * res * a % Mod;
    a = 1ll * a * a % Mod, b >>= 1;
  }
  return res;
}
const int len = 2000;
int Fac[len + 10], Iac[len + 10];
void facInit() {
  Fac[0] = Iac[0] = 1;
  for (int i = 1; i <= len; ++i) Fac[i] = 1ll * Fac[i - 1] * i % Mod;
  Iac[len] = Pow(Fac[len], Mod - 2);
  for (int i = len - 1; i; --i) Iac[i] = 1ll * Iac[i + 1] * (i + 1) % Mod;
}
int Binom(int x, int y) {
  return x < y ? 0 : 1ll * Fac[x] * Iac[y] % Mod * Iac[x - y] % Mod;
}
const int N = 2e3 + 10, K = 55;
int n, k;
int L[N], R[N];
int G[2][N][N], Pre[2][N][N];
bool checkI(int pos, int i) { return pos >= L[i] && pos <= R[i]; }
int calcG() {
  if (checkI(1, 1)) G[0][1][1] = 1;
  if (checkI(0, 1)) G[0][1][0] = 1;
  for (int mex = L[1]; mex <= R[1]; ++mex) {
    Pre[0][1][mex] = G[0][1][mex];
    if (mex) Add(Pre[0][1][mex], Pre[0][1][mex - 1]);
  }
  int cur = 0;
  for (int pos = 2; pos <= n; ++pos) {
    cur ^= 1;
    for (int sum = 0; sum <= pos; ++sum)
      for (int mex = L[pos - 2]; mex <= R[pos - 2] && mex <= sum; ++mex)
        G[cur][sum][mex] = Pre[cur][sum][mex] = 0;
    for (int sum = 0; sum <= pos; ++sum) {
      for (int mex = L[pos]; mex <= R[pos]; ++mex) {
        if (mex > sum) break;
        Add(G[cur][sum][mex], 1ll * sum * G[cur ^ 1][sum][mex] % Mod);
        if (sum) Add(G[cur][sum][mex], G[cur ^ 1][sum - 1][mex] % Mod);
        if (mex)
          Add(G[cur][sum][mex], 1ll * Iac[sum - mex] *
                                    Pre[cur ^ 1][sum - 1][min(
                                        mex - 1, min(sum - 1, R[pos - 1]))] %
                                    Mod);
        Pre[cur][sum][mex] = 1ll * Fac[sum - mex] * G[cur][sum][mex] % Mod;
        if (mex) Add(Pre[cur][sum][mex], Pre[cur][sum][mex - 1]);
      }
    }
  }
  return cur;
}
int calc(int cur) {
  int res = 0;
  for (int sum = 0; sum <= n; ++sum)
    for (int mex = L[n]; mex <= R[n]; ++mex) {
      if (mex > sum) continue;
      int coe = 1ll * Fac[n - mex] * Iac[n - sum] % Mod;
      Add(res, 1ll * G[cur][sum][mex] * coe % Mod);
    }
  return res;
}
void Work() {
  facInit();
  read(n), read(k);
  for (int i = 1, b; i <= n; ++i)
    read(b), R[i] = min(i, b + k), L[i] = max(0, b - k);
  printf("%d\n", calc(calcG()));
}
int main() { Work(); }

### 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;
void read(int& x) {
  static char c;
  int f = 0;
  while (!isdigit(c = getchar()))
    if (c == '-') f = 1;
  x = c ^ 48;
  while (isdigit(c = getchar())) x = (x * 10) + (c ^ 48);
  if (f) x = -x;
}
void read(long long& x) {
  static char c;
  int f = 0;
  while (!isdigit(c = getchar()))
    if (c == '-') f = 1;
  x = c ^ 48;
  while (isdigit(c = getchar())) x = (x * 10) + (c ^ 48);
  if (f) x = -x;
}
void read(unsigned int& x) {
  static char c;
  while (!isdigit(c = getchar()))
    ;
  x = c ^ 48;
  while (isdigit(c = getchar())) x = (x * 10) + (c ^ 48);
}
void read(unsigned long long& x) {
  static char c;
  while (!isdigit(c = getchar()))
    ;
  x = c ^ 48;
  while (isdigit(c = getchar())) x = (x * 10) + (c ^ 48);
}
void chkmax(int& x, int y) {
  if (y > x) x = y;
}
void chkmin(int& x, int y) {
  if (y < x) x = y;
}
void chkmax(long long& x, long long y) {
  if (y > x) x = y;
}
void chkmin(long long& x, long long y) {
  if (y < x) x = y;
}
void chkmax(unsigned int& x, unsigned int y) {
  if (y > x) x = y;
}
void chkmin(unsigned int& x, unsigned int y) {
  if (y < x) x = y;
}
void chkmax(unsigned long long& x, unsigned long long y) {
  if (y > x) x = y;
}
void chkmin(unsigned long long& x, unsigned long long y) {
  if (y < x) x = y;
}
const int Mod = 998244353;
void Add(int& x, int y) { (x += y) >= Mod ? x -= Mod : x; }
void Del(int& x, int y) { (x -= y) < 0 ? x += Mod : x; }
int Pow(int a, int b) {
  int res = 1;
  while (b) {
    if (b & 1) res = 1ll * res * a % Mod;
    a = 1ll * a * a % Mod, b >>= 1;
  }
  return res;
}
const int len = 2000;
int Fac[len + 10], Iac[len + 10];
void facInit() {
  Fac[0] = Iac[0] = 1;
  for (int i = 1; i <= len; ++i) Fac[i] = 1ll * Fac[i - 1] * i % Mod;
  Iac[len] = Pow(Fac[len], Mod - 2);
  for (int i = len - 1; i; --i) Iac[i] = 1ll * Iac[i + 1] * (i + 1) % Mod;
}
int Binom(int x, int y) {
  return x < y ? 0 : 1ll * Fac[x] * Iac[y] % Mod * Iac[x - y] % Mod;
}
const int N = 2e3 + 10, K = 55;
int n, k;
int L[N], R[N];
int G[2][N][N], Pre[2][N][N];
bool checkI(int pos, int i) { return pos >= L[i] && pos <= R[i]; }
int calcG() {
  if (checkI(1, 1)) G[0][1][1] = 1;
  if (checkI(0, 1)) G[0][1][0] = 1;
  for (int mex = L[1]; mex <= R[1]; ++mex) {
    Pre[0][1][mex] = G[0][1][mex];
    if (mex) Add(Pre[0][1][mex], Pre[0][1][mex - 1]);
  }
  int cur = 0;
  for (int pos = 2; pos <= n; ++pos) {
    cur ^= 1;
    for (int sum = 0; sum <= pos; ++sum)
      for (int mex = L[pos - 2]; mex <= R[pos - 2] && mex <= sum; ++mex)
        G[cur][sum][mex] = Pre[cur][sum][mex] = 0;
    for (int sum = 0; sum <= pos; ++sum) {
      for (int mex = L[pos]; mex <= R[pos]; ++mex) {
        if (mex > sum) break;
        Add(G[cur][sum][mex], 1ll * sum * G[cur ^ 1][sum][mex] % Mod);
        if (sum) Add(G[cur][sum][mex], G[cur ^ 1][sum - 1][mex] % Mod);
        if (mex)
          Add(G[cur][sum][mex], 1ll * Iac[sum - mex] *
                                    Pre[cur ^ 1][sum - 1][min(
                                        mex - 1, min(sum - 1, R[pos - 1]))] %
                                    Mod);
        Pre[cur][sum][mex] = 1ll * Fac[sum - mex] * G[cur][sum][mex] % Mod;
        if (mex) Add(Pre[cur][sum][mex], Pre[cur][sum][mex - 1]);
      }
    }
  }
  return cur;
}
int calc(int cur) {
  int res = 0;
  for (int sum = 0; sum <= n; ++sum)
    for (int mex = L[n]; mex <= R[n]; ++mex) {
      if (mex > sum) continue;
      int coe = 1ll * Fac[n - mex] * Iac[n - sum] % Mod;
      Add(res, 1ll * G[cur][sum][mex] * coe % Mod);
    }
  return res;
}
void Work() {
  facInit();
  read(n), read(k);
  for (int i = 1, b; i <= n; ++i)
    read(b), R[i] = min(i, b + k), L[i] = max(0, b - k);
  printf("%d\n", calc(calcG()));
}
int main() { Work(); }

```