Griffith's Tangled Fish Bowls

Time limit: 2000 msMemory limit: 256 MB

Griffith has built a network of $N$ rooms connected by corridors. The network is a tree. Room $i$ contains a bowl with $F_i$ fish.

Exactly $K$ distinct rooms are chosen uniformly at random from all possible sets of $K$ rooms, and one cat is placed in each chosen room. The cats then stretch a string between every unordered pair of cats. Each string follows the unique simple path between its pair of rooms.

The bowl in room $v$ spills if room $v$ is an internal room of the path between at least one pair of cats. In other words, for at least one string, the path enters and leaves room $v$ through two distinct corridors. Merely being an endpoint of a string does not make the bowl spill.

The total spill is the sum of $F_v$ over all rooms whose bowls spill. Find the expected total spill, modulo $10^9+7$ .

Input

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

Output

Let the expected total number of spilled fish, written in lowest terms, be $\frac{x}{y}$ . Print

x \cdot y^{-1} \bmod P,

Samples

Sample 1

Input

Output

333333338

There are three equally likely placements: $\{1,2\}$ , $\{1,3\}$ , and $\{2,3\}$ . Only placement $\{1,3\}$ spills the bowl in room , so the expected spill is , represented modulo as .

Griffith's Tangled Fish Bowls

Input

Output

Samples

Sample 1

Submit

Submissions

Sample 2