Gats and the Tangled Tags

Time limit: 2000 msMemory limit: 256 MB

Gats has tied $N$ lettered tags along a piece of yarn. Reading from left to right, their letters form a string $S$ .

Gats performs the following random experiment exactly once:

He chooses a set $\mathcal U \subseteq \{1,2,\ldots,N\}$ with $\lvert \mathcal U \rvert=K$ , uniformly among all such sets.
He chooses a bijection $\pi:\mathcal U\to\mathcal U$ uniformly among the $K!$ possible bijections.
A resulting string $T$ is formed as follows:

T_i= \begin{cases} S_{\pi(i)}, & i\in\mathcal U,\\ S_i, & i\notin\mathcal U. \end{cases}

The tags are treated as distinct when choosing the bijection, even when some of them carry the same letter.

The score of the resulting string is the number of adjacent pairs with equal letters:

X=\left\lvert\left\{i\mid 1\le i<N,\ T_i=T_{i+1}\right\}\right\rvert.

Find the expected value of $X$ modulo $998244353$ .

Input

The first line contains two integers $N$ and $K$ ( $2 \le N \le 2 \cdot 10^5$ , ), the number of tags and the number of selected positions.

Output

Let the expected score be the rational number $A/B$ in lowest terms. Print

A \cdot B^{-1} \bmod 998244353,

where is the multiplicative inverse of modulo . The constraints guarantee that this inverse exists.

Samples

Sample 1

Input

3 2
aba

Output

332748118

There are six equally likely pairs of a selected set and a bijection. Their scores sum to $2$ , so the expected score is $1/3$ . Its required residue is $332748118$ .

Sample 2

Input

4 4
aabc

Output

499122177

All four positions are selected. The expected score after the random bijection is $1/2$ , whose required residue is $499122177$ .

Gats and the Tangled Tags

Input

Output

Samples

Sample 1

Sample 2

Submit

Submissions

Sample 3