Non‐Intersecting Production Ranges Arrangement

You are given N military camps (numbered 1 through N) and an integer interval [1, M] on the number line. Camp i has a production range parameter r_i. If a camp is placed at an integer position x (with 1 ≤ x ≤ M), then it will produce its "good brothers" in the interval

\( [x - r_i + 1,\; x + r_i - 1] \).

There are two types of restrictions:

• If type = 0: the entire production range of every camp must lie within [1, M]. That is, a camp with parameter r_i when placed at x must satisfy \( x - r_i + 1 \ge 1 \) and \( x + r_i - 1 \le M \), i.e. \( x \in [r_i, M-r_i+1] \).
• If type = 1: the camp’s position must lie in [1, M], but its production range is allowed to extend beyond [1, M].

In addition, to avoid overcrowding the good brothers, the production ranges of any two camps (when considered as intervals) must not intersect. (Note that if two intervals share an endpoint, they are considered non‐intersecting.)

Two arrangements are considered different if there exists a camp i that is placed at different positions in the two arrangements.

Count the number of valid placement schemes modulo 998244353.

inputFormat

The first line contains three integers: N, M and type.

The second line contains N integers: r₁, r₂, ..., r_N.

Note:

• When type = 0, for each camp i its allowed placement positions are in the interval \( [r_i, M-r_i+1] \).
• When type = 1, the allowed placement positions are [1, M].

The production interval for a camp placed at x with parameter r is \( [x-r+1, x+r-1] \), and for any two camps with positions x and y (assume x is to the left of y), the non-intersection condition is:

\( x + r_x - 1 < y - r_y + 1 \)    (or equivalently, \( x + r_x \le y - r_y + 1 \)).

outputFormat

Output a single integer representing the number of valid arrangements modulo 998244353.

sample

1 5 0
2

3