N. Number of Strings
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given three integers $$$N$$$, $$$K$$$, and $$$A$$$. Your task is to calculate the number of strings of length $$$N$$$ that contain exactly $$$K$$$ palindromic substrings of length $$$3$$$, considering that each string is formed using only the first $$$A$$$ letters of the alphabet.

A substring is a string that can be obtained from the original string by deleting some characters (possibly zero) from the beginning and some characters (possibly zero) from the end.

Two or more substrings formed by the same letters in the same order, but appearing in different positions of the original string of length $$$N$$$, are not counted as the same; instead, each occurrence is counted once. For example, AAABAAA has $$$5$$$ substrings of length $$$3$$$.

A palindrome is a string that is the same if we read it from left to right or from right to left, such as SOMOS or NEUQUEN.

Input

A single line with three integers $$$N$$$, $$$K$$$, and $$$A$$$ ($$$1 \le N \le 10^{6}$$$, $$$0 \le K \le 10^{6}$$$, $$$2 \le A \le 26$$$).

Output

A single integer, the number of strings that satisfy the conditions modulo $$$998244353$$$.

Examples
Input
3 1 2
Output
4
Input
5 2 3
Output
54
Input
2 1 26
Output
0
Note

In the first example, the four strings that satisfy the conditions are AAA, ABA, BAB, and BBB. Note that all of them have exactly one palindromic substring of length $$$3$$$.

In the second example, some strings that satisfy the conditions are CACAB or ABACA.

In the third example, there are no strings that satisfy all the conditions.