Сяо Ай предложила Сяо Лань задачу: в сетке $n\times n$ в каждой клетке записано целое число от $1$ до $c$. Сколько существует способов заполнения сетки таких, что в каждой строке встречается как минимум два различных числа, и в каждом столбце встречается как минимум два различных числа?
Сяо Лань, только что изучившая комбинаторику, быстро решила эту задачу.
Тогда Сяо Ай усложнила её: сколько существует способов, если все числа на главной диагонали (где $i=j$) должны быть равны $1$?
Помогите Сяо Лань вычислить ответ по модулю $998244353$.
Входные данные
В единственной строке записаны два целых положительных числа $n$ и $c$, как описано в условии.
Выходные данные
Выведите одно число — количество способов по модулю $998244353$.
Примеры
Пример 1
Входные данные
2 3
Выходные данные
4
Пример 2
Входные данные
3 3
Выходные данные
416
Пример 3
Входные данные
5 2
Выходные данные
592260
Подзадачи
Для $100\%$ данных гарантируется, что $2\le n\le 10^6, 2\le c\le 10^8$.
| Тест | $1,2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ |
|---|---|---|---|---|---|---|---|---|---|
| $n=$ | $2$ | $5$ | $50$ | $200$ | $500$ | $2000$ | $5000$ | $10^5$ | $10^6$ |