Description

"My good brothers are endless, while your Zerg are dying every moment."

As a newly appointed commander who cares about the people, Polaris_Dane fully understood Commander Raynor's wisdom and decided to carry out this tactic to the end.

There are $N$ barracks, numbered $1,2,3\cdots N$ in order. Now you need to place them on a number line at integer points within $[1,M]$. Each barracks has a production range $r_i$. If a barracks is placed at point $x\ (1 \le x \le M)$, then it will produce good brothers on the interval $[x - r_i + 1, x + r_i - 1]$.

When $\rm type = 0$, the production range must be completely contained in the interval $[1,M]$. When $\rm type = 1$, the production range may go outside $[1,M]$, but the barracks must be placed within $[1,M]$.

Polaris_Dane cannot let the good brothers be too crowded, so the production ranges of any two barracks must not intersect. He wants to know how many placements satisfy this condition.

If there exists a barracks with index $i$ whose placement positions are different in two placements, then the two placements are considered different.

Since the answer may be very large, output the result modulo $998244353$.

Input Format

The first line contains three integers $N, M, \mathrm{type}$, where $\rm type \in \{0, 1\}$.

The second line contains $N$ integers $r_1, r_2, r_3, \ldots, r_n$.

Output Format

Output one integer in a single line: the required answer modulo $998244353$.

4 4 0
1 1 1 1

24

4 4 1
1 1 1 1

24

3 47 1
4 8 9

10940

8 100000 1
21 37 23 13 32 22 9 39

405170260

Hint

Explanation of the samples:

In Sample 1, no matter how you place the barracks, the production ranges will not overlap, so the answer is $A_4^4 = 24$.

In Sample 2, although the production ranges may go out of bounds, the barracks still have only $4$ possible positions, so the answer is still $A_4^4 = 24$.

Constraints for all testdata:

• $1 \le N, M \le 10^6$.
• $1 \le r_i \le 1000$.

This problem uses bundled tests.

• Idea: Polaris_Dane.
• Solution: Polaris_Dane.
• Code: Polaris_Dane.
• Data: Polaris_Dane.

Translated by ChatGPT 5