Distribute n Items With Lower Bounds on Each Bin

In the Resource Allocation Office of Prime City, the Manager must distribute n identical resources among k departments, where each department i requires at least li resources. By transforming variables (yi = xi - li), this reduces to a standard Stars and Bars problem. "Subtract the lower bound from each variable," the Manager says. "Let yi = xi - li, so yi >= 0. The equation becomes y1 + y2 + ... + yk = n - sum(li). If n < sum(li), there are no valid distributions." Given n, k, and k lower bounds l1, l2, ..., lk, count the number of ways to distribute n identical items among k bins where each bin i gets at least li items. Output the count modulo 10^9 + 7. If n < sum of lower bounds, output 0. Constraints: 0 <= n <= 10^6, 1 <= k <= 10^6, 0 <= li <= 10^6 Input: 10 3 1 2 3 Output: 10 Input: 3 2 2 2 Output: 0