Shared code

#include <bits/stdc++.h>
using namespace std;

#define F                       first
#define S                       second
typedef long long               ll;
ll gcd(ll a, ll b)              {return b == 0 ? a : gcd(b, a % b);}

ll inf = 1000000000;
int dp[1000001][101];
int mod = 1000000000+7;

int combination(int sum, int j, vector<int>&coin, int n){
    if(j<0) return 0;
    if(sum==0) return 1;
    if(sum<0) return 0;
    if(dp[sum][j]!=-1) return dp[sum][j];
    int count = 0;
    count+=combination(sum-coin[j],j,coin,n); count%=mod;
    count+=combination(sum,j-1,coin,n);       count%=mod;
    return dp[sum][j] = count;
}


void solve(){
     int sum,n;
     cin>>n>>sum;
     vector<int> coin(n,0);
     for(int i=0;i<n;i++){
        cin>>coin[i];
     }
     memset(dp,-1,sizeof(dp));
     sort(coin.begin(),coin.end());
     combination(sum,n-1,coin,n);
     cout << dp[sum][n-1];
}


int main(){

    ios_base::sync_with_stdio(0) ;
    cin.tie(0) ; cout.tie(0) ;
    cout.precision(20);

    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif 

    int T=1; //cin>>T;
    while(T--){
        solve();
        if(T)cout << endl;
    }

    return 0;
}