Cats from Two Directions

Time limit: 2000 msMemory limit: 256 MB

Gats is hunting mice in a network of tunnels. The network is a tree with $N$ vertices. At vertex $i$ , there are $M_i$ mice.

Exactly $K$ distinct vertices are chosen uniformly at random from all $K$ -element subsets of the vertices, and one cat is placed at each chosen vertex.

The mice at a vertex $v$ sound an alarm if both of the following conditions hold:

No cat is placed at $v$ .
After removing $v$ and every tunnel incident to $v$ , the cats occupy vertices in at least two of the resulting connected components.

If the mice at $v$ sound an alarm, all $M_v$ mice at that vertex are counted. Otherwise, none of them are counted.

Find the expected total number of mice that sound the alarm.

Input

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

Output

Let the expected total number of mice that sound the alarm be represented as $x/y$ , where $x$ and $y$ are integers and $y\not\equiv 0\pmod{998244353}$ .

Samples

Sample 1

Input

Output

Only the mice at vertex $1$ can sound the alarm. Their contribution gives an expected total of $6$ mice.

Sample 2

Input

Output

665496236

The expected number of mice sounding the alarm is $2/3$ . Its required representation modulo $998244353$ is $665496236$ .

Cats from Two Directions

Input

Output

Samples

Sample 1

Sample 2

Submit

Submissions