class Solution {
public:
    int profitableSchemes(int G, int P, vector<int>& group, vector<int>& profit) {
        const int MOD = 1000000007;
        int n = group.size();
        //dp[i][j][k] represents the ways we can get profit k
        //with j people in tasks [0, i]
        //dp[i][j][k] = dp[i - 1][j][k] + dp[i - 1][j - group[i]][k - profit[i]]
        unordered_map<int, unordered_map<int, unordered_map<int, int>>> dp;
        for(int i = 0; i < n; ++i)
        {
            if(i)dp[i] = dp[i - 1];
            int currG = group[i], currP = profit[i];
            if(currG <= G)++dp[i][currG][currP];
            for(auto& p1 : dp[i - 1])
            {
                int usedG = p1.first;
                if(currG <= G - usedG)
                {
                    for(auto& p2 : p1.second)
                    {
                        int gainedProfit = p2.first;
                        dp[i][currG + usedG][gainedProfit + currP] += p2.second;
                        dp[i][currG + usedG][gainedProfit + currP] %= MOD;
                    }
                }
            }
        }
        int res = 0;
        for(const auto& p1 : dp[n - 1])
        {
            for(const auto& p2 : p1.second)
            {
                if(p2.first >= P)
                {
                    res += p2.second;
                    res %= MOD;
                }
            }
        }
        return res;
    }
};