D. Dungeons and Dragons
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Audrey and Bastian are about to start on an epic dungeon crawl where they'll face $$$R$$$ monsters ($$$1 \le R \le 10^9$$$). Each monster has a health point (HP) value between $$$0$$$ and $$$N$$$ ($$$1 \le N \le 5 \times 10^5$$$).

Game Rules

The battle proceeds in turns, with Audrey going first:

  • On each turn, the current player selects a monster with HP $$$ \gt 0$$$
  • If the chosen monster has HP $$$= x$$$, the player can choose to deal damage $$$d$$$ where $$$1 \le d \le p[x]$$$. It's guaranteed that $$$1 \le p[x] \le x$$$ for all $$$x$$$.
  • The monster's HP becomes $$$x - d$$$
  • The player who defeats the last monster (reduces the last non-zero HP to $$$0$$$) wins

Both players play optimally.

The Setup Phase

Audrey's Preparation: Audrey, being a cunning adventurer, prepares the dungeon in advance. She sets the initial HP of all $$$R$$$ monsters to values $$$a_1, a_2, \ldots, a_R$$$ where $$$0 \le a_i \le N$$$. Audrey configures the monsters such that she is guaranteed to win if the game proceeds with these HP values.

Bastian's Sabotage: Bastian discovers Audrey's scheme and decides to sabotage exactly one monster before the battle begins. He chooses one monster with HP $$$= a_i$$$ where $$$a_i \ge K$$$ and decreases its HP by $$$K$$$, making its new HP equal to $$$a_i - K$$$.

Bastian's goal is to turn the tables and guarantee his own victory. If there's no way for Bastian to choose a monster that guarantees his win, Bastian abandons the dungeon (the game doesn't happen).

You have to determine how many distinct configurations $$$(a_1, a_2, \ldots, a_R)$$$ are possible on the final day (after Bastian's sabotage, if the game proceeds).

Important: Count configurations based on the HP values after Bastian's modification, not the initial values Audrey set.

Two configurations are considered different if they contain different HP values or the same HP values in different orders (e.g., $$$(1, 3, 2) \neq (1, 2, 3)$$$)

Input

The first line contains three integers $$$N$$$, $$$K$$$, and $$$R$$$ — the maximum HP value, the maximum reduction amount, and the number of monsters.

The second line contains $$$N$$$ integers $$$p[1], p[2], \ldots, p[N]$$$ — where $$$p[i]$$$ is the maximum damage that can be dealt to a monster with $$$i$$$ HP.

Output

Output a single integer — the number of possible monster HP configurations on the final day, modulo $$$998244353$$$.

Examples
Input
10 3 1
1 2 1 2 1 3 4 5 4 5
Output
2
Input
10 3 3
1 2 1 2 1 3 4 5 4 5
Output
194
Note

Sample Input 1 


10 3 1
1 2 1 2 1 3 4 5 4 5

Sample Output 1 


2

Explanation 1

With $$$R = 1$$$ monster, the possible configurations on the final day are single-monster configurations. The valid final configurations are $$$(3)$$$ and $$$(5)$$$, giving us $$$2$$$ possible configurations.

Sample Input 2 


10 3 3
1 2 1 2 1 3 4 5 4 5

Sample Output 2 


194

Explanation 2

One example of a valid final day configuration is $$$(1, 7, 2)$$$. This configuration could arise from:

  • Audrey initially choosing $$$(1, 7, 5)$$$, then Bastian reducing the monster with HP $$$= 5$$$ by $$$K = 3$$$ to get HP $$$= 2$$$
  • Audrey initially choosing $$$(1, 10, 2)$$$, then Bastian reducing the monster with HP $$$= 10$$$ by $$$K = 3$$$ to get HP $$$= 7$$$

In both cases, the initial configuration guarantees Audrey's win, but after Bastian's sabotage, the final configuration $$$(1, 7, 2)$$$ guarantees Bastian's win. The total number of such valid final configurations is $$$194$$$.