Background

At the FJCPC contest venue, you stare at the problem on the screen, your fingers flying over the keyboard, but there is a trace of panic in your heart. Because before you submitted your leave request, Teacher Zhou, who teaches "Advanced Situational Oral English," had given you an ultimatum.

Teacher Zhou's required weekend course is a nightmare for computer science students. Facing the thick stack of leave requests you handed in, she didn't even raise her head and fired off a classic line: "Babies, this course has an extremely heavy workload; it is very normal to ask for leave and fail. If you can't learn English well, you don't deserve to study computer science!"

In order to specially "take care of" the students, including you, who had landed on the "special list" because they asked for leave to participate in programming competitions, Teacher Zhou invented a cruel "special make-up exam knockout listening test" at the end of the semester.

Description

Suppose there are $n$ students this semester who asked for leave on weekends to participate in various programming competitions. To ensure that the knockout test runs smoothly, Teacher Zhou requires $n\ge 3$ and $n$ is odd.

The $i$-th student has an initial oral score $a_i$, assigned based on their usual performance in class, which they attended only occasionally, where $1\le a_i\le m$.

During the make-up exam, Teacher Zhou repeatedly conducts "three-person leaderless group interviews" until only one "chosen one" remains on the list and can pass; the others have their fate of "it is normal to fail after asking for leave" confirmed.

The rules for each interview are as follows:

• Teacher Zhou arbitrarily selects three students from those who have not yet been eliminated to come on stage.
• Let the oral scores of these three students, in nondecreasing order, be $p\le q\le r$.
• The student with the lowest score is eliminated.
• The student with the highest score is also eliminated.
• Only the student whose score is the median $q$ survives this round.

If several students have the same score, the above rules are still executed as "among the three selected students, delete one smallest score and one largest score, and keep one median score."

The surviving student keeps their original score; no new scores are produced during the interview process. Since each interview eliminates two students and $n$ is odd, eventually exactly one student will remain.

For a fixed initial score sequence, different choices of the group of three students and different interview orders may lead to different final survivors and different final scores.

Define the possible passing score set of an initial score sequence as the set of scores of the final survivor over all possible interview orders.

Now, this is already the sixth time you are retaking this course because you failed it. You must help Teacher Zhou calculate:

How many initial score sequences of length $n$ with $1\le a_i\le m$ are there such that the size of their possible passing score set is exactly $k$?

Since the answer may be very large, output the answer modulo $998244353$.

Input

The input contains one line with three integers $n,m,k$ ($3\le n\le 2\times 10^5$, $n$ is odd, $1\le m\le 10^9$, $1\le k\le 2\times 10^5$). They denote, respectively, the length of the initial score sequence, the upper bound of each score, and the required size of the possible passing score set.

Output

Output an integer, representing the number of initial score sequences satisfying the condition, modulo $998244353$.

Examples

Input 1

3 2 1

Output 1

8

Note

In the first sample, $n=3$, $m=2$, $k=1$.

At this time, all $2^3=8$ initial score sequences are as follows:

These $8$ sequences all have a possible passing score set of size exactly $1$, so the answer is $8$.

Input 2

7873 1980283 87783

Output 2

0

Input 3

139 541502 30

Output 3

771771379