背包问题求方案数

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int MAXX = 1e3 + 5, MOD = 1e9 + 7;

int n, v, a[MAXX], b[MAXX], sum[MAXX], dp[MAXX];

signed main(){
    cin >> n >> v;
    sum[0] = 1;
    for(int i = 1; i <= n; i++){
        cin >> a[i] >> b[i];
        for(int j = v; j >= a[i]; j--){
            int ss = dp[j];
            int x = max(dp[j], dp[j - a[i]] + b[i]), num = 0;
            if(dp[j] == x){
                num = (num + sum[j]) % MOD;
            }
            if(x == dp[j - a[i]] + b[i]){
                num = (num + sum[j - a[i]]) % MOD;
            }
            dp[j] = x;
            sum[j] = num;
        }
    }
    int ans = 0;
    for(int i = 0; i <= v; i++){
        if(dp[i] == dp[v]){
            ans = (ans + sum[i]) % MOD;
        }
    }
    cout << ans << '\n';



    return 0;
}