Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

combinatorics

dp

implementation

*3200

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. MEX counting

time limit per test

4 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputFor 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, \ldots, b_n]$$$.

Find the number of arrays $$$[a_1, a_2, \ldots, a_n]$$$, for which the following conditions hold:

$$$0 \le a_i \le n$$$ for each $$$i$$$ for each $$$i$$$ from $$$1$$$ to $$$n$$$.

$$$|MEX([a_1, a_2, \ldots, a_i]) - b_i| \le 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 \le n \le 2000$$$, $$$0 \le k \le 50$$$).

The second line of the input contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$-k \le b_i \le 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

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/09/2024 09:31:26 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|