Combinations under a modulus

Problem

Count the ways to choose r items out of n. The answer can be huge, so print it modulo 1,000,000,007.

Example

Input

5 2

Output

Ten ways.

Try the problem first. Open one hint at a time.

Hint 1

C(n, r) is the product of r numbers on top divided by r factorial.

Hint 2

Division under the modulus is multiplication by pow(den, -1, MOD); the modulus is prime.

Write your Python code, run it on the examples and submit it to hidden tests.