The King of Louse Country, the great NIT, plans to develop the economy of Louse Country. There are $n$ cities in Louse Country. There is a road between city $i$ and city $i+1$ for each $1 \leq i < n$, and there is also a road between city $n$ and city $1$.

The great NIT is a hands-on king. He drives a truck with a capacity of $m$ units of goods to trade in Louse Country, starting from city $1$, traveling along the roads through cities $2, 3, \ldots, n$, and finally returning to city $1$.

The great NIT initially carries some goods. When the great NIT arrives at a city along the road, if the truck currently has $x$ units of goods, he will purchase $\min(m-x, K)$ units of goods, and then sell some number of units (he may also choose to sell none). To prevent emergencies, the great NIT cannot sell all his inventory. Furthermore, the great NIT wishes to leave city $1$ at the end with the same amount of goods he initially carried, to facilitate future actions.

Note that the great NIT does not trade at city $1$ when he departs, but he will perform a trade when he returns to city $1$ at the end. The initial cargo load can be any integer from $1$ to $m$; he cannot start empty.

The great NIT wants to know how many different trading plans he has. Two plans are different if and only if the number of goods sold at some city is different or the initial cargo load is different. Since the number of plans is very large, you only need to output the answer modulo $998244353$.

Input

A single line containing three non-negative integers $n, m, K$.

Output

A single line containing an integer representing your answer, modulo $998244353$.

Examples

Input 1

2 3 1

Output 1

7

Note 1

The valid plans are $(1,1), (2,2), (3,3), (1,2), (2,1), (2,3), (3,2)$, totaling $7$ types, where $(x, y)$ denotes the cargo load when leaving city $1$ and city $2$ respectively.

Input 2

40 100 10

Output 2

443737370

Note 2

You can calculate this using a brute-force approach.

Constraints

For all data, $2 \leq n \leq 10^9, 1 \leq m \leq 10^9, 0 \leq K \leq 10$. Please pay attention to the data ranges of the subtasks.