Степані грає в сугороку, настільну гру. На дошці \(N+1\) квадратів, пронумерованих від 0 до \(N\).

Степан починає з квадрата 0 і йде до квадрата \(N\). У грі використовується колесо рулетки з \(M\) числами від 1 до \(M\), які з’являються з рівною ймовірністю. Степан обертає колесо та рухається на кількість клітинок, указану колесом. Якщо це виведе його за межі квадрата \(N\), він розвернеться на квадраті \(N\) і повернеться назад на надмірну кількість квадратів.

Наприклад, припустимо, що \(N=4\), а Степан знаходиться в квадраті 3. Якщо колесо показує 4, надмірна кількість квадратів поза квадратом 4 становить 3+4-4=3. Таким чином, він повертається на три клітини з квадрата 4 і приходить до квадрата 1.

Коли Степан прибуває на квадрат \(N\), він виграє, і гра закінчується.

Знайти ймовірність за модулем 998244353 того, що Степаан виграє, якщо він зможе обертати колесо не більше \(K\) разів.

Як вивести ймовірність за модулем 998244353?

Можна довести, що шукана ймовірність завжди є раціональним числом. Крім того, згідно з обмеженнями цієї задачі, коли шукану ймовірність представлено у вигляді нескоротного дробу \(\frac{y}{x}\), гарантовано, що \(x\) не ділиться на 998244353. Тут існує унікальне ціле число \(z\) між 0 і 998244352 таке, що \(xz \equiv y \pmod{998244353}\). Виведіть цей \(z\).

Обмеження

• \(M \leq N \leq 1000\)
• \(1 \leq M \leq 10\)
• \(1 \leq K \leq 1000\)
• Усі значення у вхідних даних є цілими числами.

Формат вхідних даних

Вхідний потік містить цілі числа \(N, M, K\)

Числа розділяються пропуском.

Формат вихідних даних

У вихідний потік виведіть відповідь.

Приклад вхідних даних

2 2 1

Приклад вихідних даних

499122177

Степан виграє за одне обертання, якщо колесо показує 2. Тому ймовірність виграшу становить \(\frac{1}{2}\).

Ми маємо \(2\times 499122177 \equiv 1 \pmod{998244353}\), тому відповідь 499122177.

Приклад вхідних даних

10 5 6

Приклад вихідних даних

184124175

Приклад вхідних даних

100 1 99

Приклад вихідних даних

0