Problem Description

Ling is preparing to hunt for treasures on a grid map with 2 rows and \( n+1 \) columns. She won't miss any opportunity to collect treasures.

Each cell on the grid can be either empty or wall.

Empty cells can be freely traversed, and except for the bottom of the first column, they all contain treasures. The first column of the map is always empty and serves as the entrance.

Wall cells cannot be traversed.

It is important to note that she can only move to adjacent cells, and the boundaries of the map are also impassable.

Ling is unaware of the map's configuration, but Mio says, "I know there are exactly \( k \) walls in the map. For all possible maps, how many scenarios can you collect exactly \( m \) treasures?"

"What if I don't answer?" Ling casually replies, focused only on digging for treasures.

"Well, I won't tell you about several treasure spots then," Mio says seriously. "But I won't make it too hard for you. Just give me the answer modulo \( 998244353 \)."

Ling has no choice but to ask for your help to calculate the answer.

Input Format

A single line containing three positive integers \( n \), \( k \), and \( m \).

Output Format

A single line containing an integer representing the answer.

Sample Input and Output

Input Sample #1

3 3 2

Output Sample #1

4

Input Sample #2

10 9 11

Output Sample #2

776

Input Sample #3

10 8 7

Output Sample #3

6776

Input Sample #4

233 123 114

Output Sample #4

22504357

Notes

Explanation of Sample 1

The map size is \( 2 \times (3+1) \), with 3 obstacles. There are 4 scenarios where exactly 2 treasures can be collected, as shown below:

Green parts indicate the entrance, gray indicates walls, and white indicates treasure-containing empty cells.

There are exactly 4 scenarios where the entrance leads to exactly 2 empty cells, i.e., collecting 2 treasures.

Hence, the answer is 4.

Data Range

This problem uses subtask testing.

Subtask1 (11 pts): \( n \leq 12 \);
Subtask2 (19 pts): \( n \leq 1000 \);
Subtask3 (31 pts): \( n \leq 5 \times 10^4 \);
Subtask4 (39 pts): No special restrictions.

For 100% of the data, \( 2 \le n \le 3 \times 10^6 \), \( m, k \geq 2 \), \( m + k \leq 2n \).

Hint
This is an OI problem, not a proof problem.

见题面 Input 部分

见题面 Output 部分