Рассмотрим следующий эксперимент. У вас есть колода из \(m\) карт, ровно одна из них — джокер. \(n\) раз вы производите следующие действия: перемешиваете колоду, берете верхнюю карту, просматриваете ее и возвращаете ее в колоду.
Пусть \(x\) — количество раз, когда вы брали с вершины колоды джокера. Предполагая, что при каждом перемешивании колоды все \(m!\) перестановок карт равновероятны, чему равно математическое ожидание \(x^k\)? Выведите ответ по модулю \(998244353\).
В единственной строке заданы три целых числа \(n\), \(m\) и \(k\) (\(1 \le n, m < 998244353\), \(1 \le k \le 5000\)).
Выведите одно число — математическое ожидание \(x^k\), взятое по модулю \(998244353\) (ответ всегда можно представить в виде несократимой дроби \(\frac{a}{b}\), где \(b \mod 998244353 \ne 0\); выведите \(a \cdot b^{-1} \mod 998244353\)).
1 1 1
1
1 1 5000
2 2 2
499122178
998244352 1337 5000
326459680
4000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач