All problems

Bouquet Ways

Medium · math

A flower stall sells n different kinds of flower, one stem of each kind. A customer picks exactly k of the kinds to make a bouquet. The order of the stems in the bouquet does not matter, only which kinds are in it.

You are given a list queries. Each query is a pair [n, k]: the stall has n kinds and the customer wants k of them. For every query, work out how many different bouquets are possible.

The counts can be huge, so give each one modulo 10^9 + 7: the remainder after dividing by 1000000007.

Return a list with one number per query, in the same order as queries.

Examples

Example 1

Input: queries = [[5, 2], [4, 0], [6, 3]]

Output: [10, 1, 20]

From 5 kinds there are 10 ways to choose 2. Choosing 0 kinds gives exactly one bouquet, the empty one. From 6 kinds there are 20 ways to choose 3.

Example 2

Input: queries = [[10, 5]]

Output: [252]

There are 252 ways to choose 5 kinds from 10.

Example 3

Input: queries = [[100, 50]]

Output: [538992043]

The true count has 30 digits. Its remainder after dividing by 1000000007 is 538992043.

Constraints