Problem Background

Polaris_Dane is very inexperienced. He is not only obsessed with counting but also enjoys playing StarCraft 2.

Problem Description

"My good brothers are endless, while your zerg are perishing every moment."

As a newly appointed commander who loves his people, Polaris_Dane fully understands the wisdom of Commander Raynor and decides to implement this strategy to the fullest.

There are $N$ barracks, numbered sequentially as $1, 2, 3, \ldots, N$. They need to be arranged on integer points within the interval $[1, M]$ on a number line. Each barracks has a production range $r_i$. If a barracks is placed at point $x$ ($1 \le x \le M$), it will produce good brothers within the interval $[x - r_i + 1, x + r_i - 1]$.

When $\text{type} = 0$, the production range of good brothers must be completely contained within the interval $[1, M]$. When $\text{type} = 1$, the production range can extend beyond $[1, M]$, but the barracks must be placed within $[1, M]$.

Polaris_Dane does not want the good brothers to be too crowded, so the production ranges of any two barracks must not overlap. He wants to know how many arrangements satisfy this condition.

Two arrangements are considered different if there exists a barracks with number $i$ placed at different positions in the two arrangements.

Since the answer may be very large, Polaris_Dane asks you to output the result modulo $998244353$.

Input Format

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

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

Output Format

Output a single integer, which is the result of the answer modulo $998244353$.

Sample Input and Output

Input Sample #1

4 4 0
1 1 1 1

Output Sample #1

24

Input Sample #2

4 4 1
1 1 1 1

Output Sample #2

24

Input Sample #3

3 47 1
4 8 9

Output Sample #3

10940

Input Sample #4

8 100000 1
21 37 23 13 32 22 9 39

Output Sample #4

405170260

Notes/Hints

Explanation of Samples:

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

In Sample 2, although the production ranges can extend beyond the boundaries, the possible positions for the barracks remain 4, so the answer is still $A_4^4 = 24$.

For all data:
- $1 \le N, M \le 10^6$;
- $1 \le r_i \le 1000$.

This problem uses batched testing.

见题面 Input 部分

见题面 Output 部分