CSES coin combinations 2

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using lld = long double;
using ull = unsigned long long;
using vll = vector<ll>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;

#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x<<" "; _print(x); cerr << endl;
#else
#define debug(x) ((void)0);
#endif

#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define loop(i,k,n) for(ll i = k; i < n;i++)
#define MOD 1000000007
#define nl "\n"
#define pb push_back


vll v;
ll dp[101][1000001];    // such big array not allowed gives runtime error
// is there some way i can make this into dp[2][1000001]
// but still keep this recursive (or not make much changes to recursive code)

ll f(ll i, ll j) {
    if(j == 0) return 1;
    if(i == 0) return 0;
    if(dp[i][j] != -1) return dp[i][j];
    ll op1 = ((i-1 >=0) ? f(i-1 , j) : 0);
    ll op2 = ((j-v[i] >= 0) ? f(i , j-v[i]) : 0);
    ll ans = (op1 + op2) % MOD;
    return dp[i][j] = ans;
}

void solve(){
    //testing
    ll n, sum; cin >> n >> sum;
    v.assign(n+1, 0);
    memset(dp, -1, sizeof dp);  // dp(index, sum) -> gives no of ways
    loop(i, 1, n+1) cin >> v[i];    // 1 based indexing
    // vector<vll> dp(2, vll(sum + 1));
    // loop(i, 0, n+1) {
    //     loop(j, 0, sum + 1) {
    //         if(j == 0) {
    //             dp[i&1][j] = 1;
    //         }
    //         else if(i == 0) {
    //             // j is non zero here, so no possible way
    //             dp[i&1][j] = 0;
    //         }
    //         else{
    //             ll op1 = 0, op2 = 0;
    //             op1 = (i-1 >=0) ? dp[(i-1)&1][j] : 0;
    //             op2 = (j-v[i] >= 0) ? dp[i&1][j-v[i]] : 0;
    //             dp[i&1][j] = op1 + op2;
    //             dp[i&1][j] %= MOD;
    //         }
    //     }
    // }
    cout << f(n, sum) << nl;
}

int main(){
    fastio();
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
    #endif

    int t = 1;
    // cin>>t;
    for(ll i = 1; i <= t; i ++)
    {
        solve();
    }
}