Rainbow Leap Parade

Time limit: 2000 msMemory limit: 256 MB

Gats is organizing a parade of cats. There are $N$ cats, indexed from $1$ to $N$ . Cat $i$ has jump strength $S_i$ , fur color $C_i$ , and fish reward $W_i$ . Cats with equal color values have the same fur color.

Gats forms a parade by choosing exactly $K$ distinct cats and placing them in an ordered list $(X_1,X_2,\ldots,X_K)$ . Every ordered list of distinct cats is equally likely.

For every position $t$ satisfying $2 \le t \le K-1$ , consider the consecutive trio $(X_{t-1},X_t,X_{t+1})$ . The middle cat performs a if both of the following conditions hold:

The three colors $C_{X_{t-1}}$ , $C_{X_t}$ , and are pairwise distinct.

\min(S_{X_{t-1}},S_{X_{t+1}}) < S_{X_t} < \max(S_{X_{t-1}},S_{X_{t+1}}).

Whenever a rainbow leap occurs at position $t$ , the parade earns $W_{X_t}$ fish. Contributions from different positions are counted independently, even when their trios overlap.

Find the expected total number of fish earned by the parade.

Input

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

Output

Let $P=1{,}000{,}000{,}007$ . Print the expected total number of fish earned, modulo $P$ .

For a rational number $a/b$ with $b \not\equiv 0 \pmod P$ , its value modulo is defined as .

Samples

Sample 1

Input

Output

333333338

All three colors are different. Of the $6$ possible parades, exactly $2$ have the cat of strength $2$ in the middle. Each of those parades scores $7$ fish, so the expectation is $7/3$ , whose value modulo $1{,}000{,}000{,}007$ is .

Rainbow Leap Parade

Input

Output

Samples

Sample 1

Submit

Submissions

Sample 2