Gats and the Uplifting Leaps

Time limit: 5000 msMemory limit: 256 MB

Gats is crossing a row of $N$ rooftops. Rooftop $i$ has height $H_i$ .

Exactly $K$ distinct rooftops are illuminated. Every subset of $K$ rooftops is equally likely to be illuminated. If their indices in increasing order are

p_1 < p_2 < \cdots < p_K,

Gats starts on rooftop $p_1$ and then jumps from $p_t$ to $p_{t+1}$ for every .

A jump is uplifting if its destination is strictly higher than its starting point. In other words, the jump from $p_t$ to $p_{t+1}$ is uplifting when

H_{p_{t+1}} > H_{p_t}.

Find the expected number of uplifting jumps.

Input

The first line contains two integers $N$ and $K$ ( $1 \le N \le 2 \times 10^5$ , ), the number of rooftops and the number that will be illuminated.

Output

Write the exact expected number of uplifting leaps in lowest terms as $A/B$ . Print the unique integer $R$ satisfying

0 \le R < 10^9+7

Samples

Sample 1

Input

4 2
3 1 4 2

Output

500000004

Three of the six equally likely illuminated pairs produce an uplifting leap, so the expectation is $1/2$ .

Sample 2

Input

5 3
2 5 1 4 3

Output

300000003

For the ten possible illuminated triples, the total number of uplifting leaps is $9$ , giving an expectation of $9/10$ .

Sample 3

Input

3 1
7 2 9

Output

When $K=1$ , Gats makes no leaps.