Audrey 和 Bastian 即将开始一场史诗般的地下城探险，他们将面对 $R$ 只怪物 ($1 \le R \le 10^9$)。每只怪物的生命值 (HP) 在 $0$ 到 $N$ 之间 ($1 \le N \le 5 \times 10^5$)。

游戏规则

战斗轮流进行，Audrey 先手：

• 在每一回合中，当前玩家选择一只 HP $> 0$ 的怪物。
• 如果所选怪物的 HP $= x$，玩家可以选择造成 $d$ 点伤害，其中 $1 \le d \le p[x]$。保证对于所有 $x$，都有 $1 \le p[x] \le x$。
• 怪物的 HP 变为 $x - d$。
• 击败最后一只怪物的玩家（将最后一只非零 HP 的怪物 HP 减至 $0$）获胜。

双方均采取最优策略。

准备阶段

Audrey 的准备：作为一名狡猾的冒险家，Audrey 提前准备了地下城。她将所有 $R$ 只怪物的初始 HP 设置为 $a_1, a_2, \dots, a_R$，其中 $0 \le a_i \le N$。Audrey 对怪物进行配置，使得如果游戏按照这些 HP 值进行，她保证获胜。

Bastian 的破坏：Bastian 发现了 Audrey 的计划，并决定在战斗开始前破坏恰好一只怪物。他选择一只 HP $= a_i$ 且 $a_i \ge K$ 的怪物，将其 HP 减少 $K$，使其新 HP 等于 $a_i - K$。

Bastian 的目标是扭转局势并保证自己获胜。如果 Bastian 无法选择一只怪物来保证他获胜，Bastian 就会放弃地下城（游戏不会发生）。

你需要确定在最终日（如果游戏发生，即 Bastian 破坏后），有多少种不同的配置 $(a_1, a_2, \dots, a_R)$ 是可能的。

重要提示：配置的计数基于 Bastian 修改后的 HP 值，而不是 Audrey 最初设置的值。

如果两个配置包含不同的 HP 值，或者包含相同的 HP 值但顺序不同，则认为它们是不同的（例如，$(1, 3, 2) \neq (1, 2, 3)$）。

输入格式

第一行包含三个整数 $N, K$ 和 $R$ —— 最大 HP 值、最大减少量和怪物数量。

第二行包含 $N$ 个整数 $p[1], p[2], \dots, p[N]$ —— 其中 $p[i]$ 是对 HP 为 $i$ 的怪物所能造成的最大伤害。

输出格式

输出一个整数 —— 最终日可能的怪物 HP 配置数量，对 $998244353$ 取模。

样例

输入 1

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

输出 1

2

说明 1

当 $R = 1$ 只怪物时，最终日的可能配置即为单只怪物的配置。有效的最终配置为 $(3)$ 和 $(5)$，因此有 $2$ 种可能的配置。

输入 2

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

输出 2

194

说明 2

一个有效的最终日配置示例是 $(1, 7, 2)$。该配置可能源于：

• Audrey 最初选择 $(1, 7, 5)$，然后 Bastian 将 HP $= 5$ 的怪物减少 $K = 3$，得到 HP $= 2$。
• Audrey 最初选择 $(1, 10, 2)$，然后 Bastian 将 HP $= 10$ 的怪物减少 $K = 3$，得到 HP $= 7$。

在这两种情况下，初始配置都保证了 Audrey 的胜利，但在 Bastian 破坏后，最终配置 $(1, 7, 2)$ 保证了 Bastian 的胜利。此类有效的最终配置总数为 $194$。