Count Multisets of Size k From n Types

In the Botanical Garden of Prime City, the Gardener must choose k flowers from n types, where each type can be chosen multiple times (with repetition). The number of such multisets is C(n + k - 1, k) ÔÇö a direct application of Stars and Bars. "A multiset allows repetition," the Gardener explains. "Choosing k items from n types with repetition is like placing k stars into n bins. The answer is C(n + k - 1, k) = C(n + k - 1, n - 1)." Given n (number of types) and k (size of multiset), compute the number of multisets modulo 10^9 + 7. Constraints: 1 <= n <= 10^6, 0 <= k <= 10^6 Input: 3 2 Output: 6 Input: 4 3 Output: 20