Forked Yarn

Time limit: 3000 msMemory limit: 256 MB

Gats has tied yarn into a tree of $N$ knots, numbered from $1$ to $N$ . Each strand directly connects two knots.

Exactly $K$ cats choose $K$ distinct knots. Every set of $K$ knots is equally likely, and one cat occupies each chosen knot.

Consider a knot $v$ . Remove $v$ and every strand incident to it. The remaining knots are divided into one or more connected components. Knot $v$ is called forked if both of the following conditions hold:

no cat occupies knot $v$ ;
at least three of the resulting connected components each contain at least one cat.

The number of forked knots depends on the randomly chosen set of occupied knots. Find its expected value modulo $10^9+7$ .

Input

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

Output

Let $X$ be the number of forked knots after the cats choose their knots. Print the expected value $\mathbb{E}[X]$ modulo $M=10^9+7$ .

Formally, if , print the unique integer in the range through congruent to

Samples

Sample 1

Input

Output

250000002

Only the choice consisting of knots $2$ , $3$ , and $4$ makes knot $1$ forked. Therefore, the expected number of forked knots is $1/4$ .

Sample 2

Input

Output

800000006

Across the $15$ equally likely choices, knot is forked in choices and knot is forked in choices. Thus, the expected number of forked knots is .

Forked Yarn

Input

Output

Samples

Sample 1

Sample 2

Submit

Submissions