Branch-Split Breakfast

Time limit: 2000 msMemory limit: 256 MB

There are $N$ clearings connected by trails that form a tree. Clearing $i$ contains a closed station holding $A_i$ units of milk.

At night, exactly $K$ distinct clearings are selected uniformly at random from all $\binom{N}{K}$ possible sets. One cat sleeps at each selected clearing.

At dawn, each station is considered independently. For a clearing $v$ , remove $v$ and every trail incident to it. The station at $v$ opens if and only if both of the following conditions hold:

Clearing $v$ was not selected.
At least two different connected components remaining after the removal each contain at least one selected clearing.

If the station at $v$ opens, all $A_v$ units of its milk are released. Otherwise, it releases nothing.

Find the expected total amount of milk released by all stations.

Input

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

Output

Let the exact expected total amount of released milk be $E=\frac{x}{y}$ in lowest terms, where $y>0$ . Let $P =^{}$ .

Samples

Sample 1

Input

Output

For the six possible selected pairs, the released amounts are $0,2,6,0,4,0$ . Their average is $2$ .

Sample 2

Input

Output

500000005

Only selections consisting of two leaves open the station at clearing $1$ . This happens for $3$ of the possible selections, so the expected amount is , represented modulo as .

Branch-Split Breakfast

Input

Output

Samples

Sample 1

Sample 2

Submit

Submissions