CSES – Coin Combinations II

#include<bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
using namespace std;
//declare
const int mod = 1e9+7;
int n,x,dp[105][1000005];
vector<int> c;
//
signed main(){
    fastio;
    cin>>n>>x;
    c.push_back(-1);
    for(int i=0;i<n;i++){
        int a; cin>>a;
        c.push_back(a);
    }
    dp[0][0] = 1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=x;j++){
            dp[i][j] = dp[i-1][j];
            if(j-c[i] >= 0) dp[i][j] += dp[i][j-c[i]];
            dp[i][j] %= mod;
        }
    }
    cout<<dp[n][x]<<"\n";
    return 0;
}