736. Single Entry of Pascal's Triangle — C(n, k) (Modulo 10^9+7)

Given two non-negative integers n and k, return the binomial coefficient C(n, k) (the value at row n, column k of Pascal's Triangle, 0-indexed) modulo 10^9 + 7. By definition, C(n, k) = 0 when k < 0 or k > n, and C(n, 0) = C(n, n) = 1. You should derive the value using the recursive identity C(n, k) = C(n-1, k-1) + C(n-1, k) (mod 10^9 + 7), or any equivalent recursive method (memoization is allowed and recommended).

Input: Two non-negative integers n and k separated by a comma, with 0 <= k <= n.

Output: Return an integer equal to C(n, k) mod (10^9 + 7).

Examples

Input: 5, 2
Output: 10
Explanation: C(5,2) = 10.

Input: 0, 0
Output: 1
Explanation: C(0,0) = 1.

Input: 10, 3
Output: 120
Explanation: C(10,3) = 120.

Constraints

• 0 <= k <= n <= 1000

Asked by