В інформатиці символ - це буква, цифра, розділовий знак або інший подібний символ. Оскільки комп’ютери можуть обробляти лише числа, для представлення символів використовуються цифрові коди, що називається кодуванням символів. Система кодування символів встановлює бієкцію між елементами алфавіту певного розміру \(n\) і цілими числами від 0 до \(n-1\). Деякі добре відомі системи кодування символів включають Американський стандартний код для обміну інформацією (ASCII), який має розмір алфавіту 128, і розширений ASCII, який має розмір алфавіту 256.

Наприклад, у системі кодування ASCII слово \(𝚠𝚍𝚢\) закодовано як [119, 100, 121], а \(𝚓𝚜𝚠\) закодовано як [106, 115, 119]. Можна помітити, що як 119+100+121=340, так і 106+115+119=340. Насправді всього 903 таких слова довжиною 3 у системі кодування розміром алфавіту 128 (у цьому прикладі ASCII). Проблема полягає в наступному: задана система кодування розміром алфавіту \(n\), де кожен символ закодований як число від 0 до \(n−1\) включно. Скільки існує різних слів довжини \(m\), щоб сума закодованих чисел усіх символів дорівнює \(k\)?

Оскільки відповідь може бути великою, вам потрібно вивести її лише за модулем 998244353.

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

Перший рядок вводу — це одне ціле число \(T\) (\(1≤T≤400\)), кількість тестів.

Кожен тест містить рядок із трьох цілих чисел \(n,m,k\) (\(1≤n,m≤10^5\),\(0≤k≤10^5\)), що позначають розмір алфавіту системи кодування, довжину слова та необхідну суму закодованих чисел усіх символів відповідно.

Гарантується, що сума \(n\), сума \(m\) і сума \(k\) не перевищують \(5×10^6\) відповідно.

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

Для кожного тесту виведіть відповідь за модулем 998244353 в окремому рядку.

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

4
2 3 3
2 3 4
3 3 3
128 3 340

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

1
0
7
903