1
class Solution:
2
    def profitableSchemes(self, n, minProfit, group, profit):
3

4
        k = len(group)
5
        arr = [
6
            [[0 for _ in range(k + 1)] for _ in range(minProfit + 1)]
7
            for _ in range(n + 1)
8
        ]
9

10
        for i in range(n + 1):
11
            arr[i][0][k] = 1
12

13
        for j in range(k - 1, -1, -1):
14
            for i in range(n, -1, -1):
15
                for x in range(minProfit, -1, -1):
16

17
                    arr[i][x][j] = arr[i][x][j + 1]
18
                    if i >= group[j]:
19
                        arr[i][x][j] += arr[i - group[j]][max(x - profit[j], 0)][j + 1]
20

21
        return arr[n][minProfit][0] % (10**9 + 7)