Purring Junctions

Time limit: 3000 msMemory limit: 256 MB

Gats has tied strings along the edges of a tree with $N$ vertices, numbered $1,2,\ldots,N$ .

Exactly $K$ cats are placed on distinct vertices. Their placement is chosen uniformly at random from all $\binom{N}{K}$ sets of $K$ vertices.

For a vertex $v$ , imagine removing $v$ and every edge incident to it. Each resulting connected component is called a branch of $v$ . A branch is occupied if it contains at least one cat.

A vertex $v$ purrs if both of the following conditions hold:

Vertex $v$ does not contain a cat.
Exactly $2$ branches of $v$ are occupied.

Each of the two occupied branches may contain any positive number of cats. Every other branch must contain no cats.

Let $X$ be the total number of purring vertices. Compute the expected value of $X$ modulo $P=10^9+7$ .

More precisely, let $A$ be the sum of $X$ over all $\binom{N}{K}$ possible placements. Output

A\cdot\binom{N}{K}^{-1}\bmod P,

where $\binom{N}{K}^{-1}$ is the modular multiplicative inverse of $\binom{N}{K}$ modulo .

Input

The first line contains two integers $N$ and $K$ , where $2 \le N \le 2 \cdot 10^5$ and .

Output

Print one integer $Y$ satisfying $0 \le Y < P$ , representing the expected number of purring vertices modulo $P=10^9+7$ .

Samples

Sample 1

Input

3 2
1 2
2 3

Output

333333336

There are $\binom{3}{2}=3$ equally likely placements. Only the placement $\{1,3\}$ makes a vertex purr, so the expectation is , represented modulo .

Purring Junctions

Input

Output

Samples

Sample 1

Sample 2