You might find this problem familiar. Do not panic.

The romantic poet Bubuliss, who loves the Longest Increasing Subsequence, also loves matrices. This might sound a bit extreme, but extremity is also a form of romance. Bubuliss has three numbers $n, q, t$, where $q$ is a prime number. For an $n \times n$ matrix $C$ over $\mathbb{F}_q$, if there are exactly $k$ pairs of $n \times n$ matrices $(A, B)$ (out of a total of $q^{2n^2}$ pairs) such that $AB = C$, then the value of $C$ is defined as $k^t$. Bubuliss wants you to calculate the sum of the values of all possible matrices (a total of $q^{n^2}$ matrices) modulo $998244353$.

If you do not know what $\mathbb{F}_q$ is, you can understand it as the set of integers $\ge 0$ and $< q$, where addition and multiplication are performed modulo $q$.

Modern Poetry Reading

You will walk toward the misty morning fog Gazing from the cloud-piercing, pale Everest peak You bury the wilderness in the twilight moonlight The path ahead disappears in the May rice fields You tell me of the eastern valley Where birds gather February orchids and green bamboo In the hilly land, in the wilderness of peach and plum blossoms in spring Mountain apricots are covered in pearls A large willow tree, damp lilacs The dew of hope brightens the mountain ridges and ponds You are a romantic poet You are the starlight in a glass bottle, shining in from outside the window

— LeafCreeper, Finding a Needle in a Haystack

Input

A single line containing three positive integers $n, q, t$, as described in the problem.

Output

A single line containing one integer, representing the answer.

Examples

Input 1

2 2 2

Output 1

6496

Input 2

10 3 2

Output 2

475440451

Input 3

1000 686902939 3

Output 3

104612575

Constraints

For all data, it is guaranteed that $2 \le n \le 10^7$, $2 \le q < 998244353$, $2 \le t \le 20$, and $q$ is a prime number.

Subtasks