Coin Combinations II

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000000007;

#define got cout<<"YES\n"; return;
#define got0 cout<<"YES\n"; return 0;

#define bhak cout<<"NO\n"; return;
#define bhak0 cout<<"NO\n"; return 0;

#define bas cout<<"\n";

vector<vector<ll>> dp(101, vector<ll> (1e6+10, -1));

ll getAns(ll i, ll sum, ll n, vector<ll> &vec){
    if(sum==0){
        return 1;
    }

    if(sum<0){
        return 0;
    }

    if(i==n){
        return 0;
    }

    if(dp[i][sum]!=-1){
        return dp[i][sum];
    }

    ll pick = getAns(i, sum-vec[i], n, vec)%MOD;
    ll notPick = getAns(i+1, sum, n, vec)%MOD;

    return dp[i][sum] = (pick + notPick)%MOD;
}

int main() {
    // your code goes here
    ll  n, sum; cin>>n>>sum;
    vector<ll> vec(n);
    for(ll i=0; i<n; ++i){
        cin>>vec[i];
    }

    ll ans = getAns(0, sum, n, vec);

    cout<<ans;
    bas

    return 0;
}