class Solution {
const int M = 1e9+7;
public:
int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
vector<vector<int>> dp(n+1, vector<int>(minProfit+1, 0));
dp[0][0] = 1;
for(int k = 0; k < group.size(); ++k) {
int x = group[k];
int y = profit[k];
auto tmp = dp;
for(int i = 0; i <= n; ++i) {
for(int j = 0; j <= minProfit; ++j) {
if(i + x <= n) {
int p = min(j + y, minProfit);
dp[i+x][p] += tmp[i][j];
dp[i+x][p] %= M;
}
}
}
}
int ret = 0;
for(int i = 0; i <= n; ++i) {
ret += dp[i][minProfit];
ret %= M;
}
return ret;
}
};
// dp[n_person][profit]: number of ways to get profit with n_person.