Binomial bouquets: hints, no solution

A florist stocks varieties different flowers and wants to know how many distinct bouquets of exactly picks different varieties can be made. Two bouquets differ if they contain a different set of varieties, and the arrangement inside a bouquet does not matter. Build the count with a table filled using only additions, where each entry comes from earlier entries, rather than with factorials or division, because the exact values are huge. Return the count modulo 1000000007.

Examples

Input

varieties = 5, picks = 2

Output

10

Note

There are 10 ways to choose 2 of 5 varieties.

Input

varieties = 4, picks = 0

Output

1

Note

The empty bouquet is the one way to pick nothing.

Input

varieties = 6, picks = 3

Output

20

Constraints

• 0 <= picks <= varieties <= 2000
• The result is reported modulo 1000000007

Hint 1: a nudge

Fix one particular variety. A bouquet either contains it or it does not. How many flowers must you still choose in each case, and from how many varieties?

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing