Profitable Schemes

You have n available members and a list of jobs. Job i needs group[i] members and earns profit[i] profit. A member may participate in at most one selected job.

A scheme is a subset of jobs whose total required members is at most n and whose total profit is at least minProfit. Return the number of such subsets, modulo 1000000007. Each job can be selected at most once. Jobs at different indices are distinct even when their requirements and profits match. The empty subset counts when minProfit is zero.

Example 1:

Input: n = 4
minProfit = 4
group = [2,3,1]
profit = [3,4,1]

Output: 3

Explanation: Selecting only job 1 earns 4 profit with 3 members. Selecting jobs 0 and 2 earns 4 with 3 members, and selecting jobs 1 and 2 earns 5 with 4 members. These are the three valid subsets.

Example 2:

Input: n = 2
minProfit = 0
group = [1,2]
profit = [0,0]

Output: 3

Explanation: The empty subset and either single job meet the zero-profit target. Selecting both jobs would require 3 members, exceeding the limit of 2. The answer is 3.

Example 3:

Input: n = 3
minProfit = 5
group = [4,2]
profit = [8,4]

Output: 0

Explanation: Job 0 requires more members than are available. Job 1 fits but earns only 4 profit, below the target of 5. No subset qualifies, so return 0.

Constraints:

• 1 <= n <= 100
• 0 <= minProfit <= 100
• 1 <= group.length <= 100
• profit.length == group.length
• 1 <= group[i] <= 100
• 0 <= profit[i] <= 100