Problem B. Judgment

It’s a beautiful day outside... Birds are singing, flowers are blooming... On days like these kids like you... SHOULD BE BURNING IN HELL.

You are an arrogant person who has arrived at the final judgment corridor to face judgment by sans.

In a judgment, sans will launch several attacks. The attacks are of $k$ types, where the $i$-th type of attack will be launched a total of $a_i$ times ($a_i$ is a non-negative integer). At the beginning of the judgment, you only know the total number of each type of attack $(a_1, a_2, \dots, a_k)$, but you do not know their specific order.

Your initial Execution Points (EP) are $1$. Before each attack launched by sans, you can formulate a response strategy. Specifically, before the $j$-th attack, let your current Execution Points be $E_j$. You can choose a set of real numbers $b_1, b_2, \dots, b_k$ that must satisfy the following two conditions:

1. $\sum_{i=1}^{k} b_i = 0$
2. For all $i \in \{1, 2, \dots, k\}$, $b_i \geq -E_j$. (Regardless of which attack sans launches, your Execution Points will not become negative.)

Subsequently, sans will choose one from the remaining attacks and launch it. If this attack is of type $l$, your Execution Points will be updated to $E_j + b_l$. After each attack ends, you will know exactly the type of that attack.

sans understands your strategy and will always choose the attack order that best suppresses you, in order to make your final Execution Points as low as possible. Your goal is to formulate an optimal strategy for choosing $b_i$ to maximize this final Execution Points in the "worst-case" scenario determined by sans.

The final Execution Points you can guarantee to obtain through this optimal game are called your Level of ViolencE (LV).

Because you are filled with determination, you will undergo all possible judgments by sans. A judgment is defined by the attack count vector $(a_1, \dots, a_k)$. All possible judgments must satisfy:

• The total number of attacks $\sum_{i=1}^{k} a_i$ is in the range $[0, M]$.
• The number of each type of attack $a_i$ does not exceed $n$, i.e., $0 \leq a_i \leq n$.

Two judgments are considered essentially different if and only if their attack count vectors $(a_1, \dots, a_k)$ are different.

You are an arrogant person, so you need to calculate the sum of your Level of ViolencE for all these judgments, modulo 998244353.

Input

A single line containing three non-negative integers $n, k, M$ ($0 \leq n \leq M \leq 10^5, 1 \leq k \leq 10^9$).

Output

Output a single integer representing the sum of your Level of ViolencE for all these judgments, modulo 998244353.

Examples

Input 1

1 2 2

Output 1

7

Input 2

11 45 14

Output 2

286390301

Note

For Example 1, you will undergo a total of 4 judgments.

• In the 1st judgment, $a_1 = a_2 = 0$, obviously your final Execution Points are 1.
• In the 2nd judgment, $a_1 = 1, a_2 = 0$. Before the 1st attack, you choose $b_1 = 1, b_2 = -1$, so your final Execution Points are 2.
• In the 3rd judgment, $a_1 = 0, a_2 = 1$. Before the 1st attack, you choose $b_1 = -1, b_2 = 1$, so your final Execution Points are 2.
• In the 4th judgment, $a_1 = a_2 = 1$. Before the 1st attack, you choose $b_1 = b_2 = 0$, which is equivalent to skipping an attack. At this point, you learn the type of the 1st attack and infer the type of the 2nd attack, denoted as type $i$, where $i \in \{1, 2\}$. Thus, before the 2nd attack, you choose $b_i = 1, b_{3-i} = -1$, so your final Execution Points are 2.

It can be proven that the final Execution Points obtained by following the above strategy are the maximum among those that can be guaranteed, so the sum of your Level of ViolencE is $1 + 2 + 2 + 2 = 7$.