Xiao Ai gave Xiao Lan a problem: in an $n \times n$ grid, where each cell contains an integer from $1$ to $c$, how many ways are there to fill the grid such that every row contains at least two different numbers, and every column contains at least two different numbers?
Having just learned how to count, Xiao Lan quickly solved this problem.
Xiao Ai then increased the difficulty: if all numbers on the main diagonal ($i=j$) must be $1$, how many ways are there?
Please help Xiao Lan calculate the answer, modulo $998244353$.
Input
A single line containing two positive integers $n$ and $c$, as described in the problem.
Output
Output a single number representing the number of ways modulo $998244353$.
Examples
Input 1
2 3
Output 1
4
Input 2
3 3
Output 2
416
Input 3
5 2
Output 3
592260
Subtasks
For $100\%$ of the data, it is guaranteed that $2\le n\le 10^6$ and $2\le c\le 10^8$.
| Data Point | $1,2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ |
|---|---|---|---|---|---|---|---|---|---|
| $n=$ | $2$ | $5$ | $50$ | $200$ | $500$ | $2000$ | $5000$ | $10^5$ | $10^6$ |