Shared code

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define endl "\n"
#define br cout<<"\n"
#define ft first
#define sd second
#define tc int t; cin>>t; while(t--)
#define naivedyam ios::sync_with_stdio(false); cin.tie(NULL);
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define input(a,n) for(int i=0;i<n;i++) cin>>a[i]
#define input_vec(vec, n) for(int i=0;i<n;i++) {int x;cin>>x;vec.push_back(x);}
#define input_matrix(mat, n, m) for(int i=0;i<n;i++) {for(int j=0;j<m;j++) {int x;cin>>x;mat[i][j]=x;}}

const int MOD = 1e9 + 7;
const int INF = LLONG_MAX>>1;
const int MAXN = 15000001;

vector<int> spf(MAXN);

void spf_sieve(vector<int>& spf){
    spf[1] = 1;
    for(int i=2;i<MAXN;i++){
        spf[i] = i;
    }
    for(int i=2;i*i<MAXN;i++){
        if(spf[i]==i){
            for(int j=i*i;j<MAXN;j+=i){
                if(spf[j]==j) spf[j]=i;
            }
        }
    }
}

int n, k;
 
using v = vector<int>;
using pr = pair<int,int>;
using mp = map<int,int>;
using um = unordered_map<int,int>;
using us = unordered_set<int>;
using st = set<int>;
using pq = priority_queue<int>;
using str = string;
using mt = multiset<int>;
using dq = deque<int>;
using vp = vector<pr>;
using matrix = vector<vector<int>>;
 
v sieve(int n) {
    vector<bool> is_prime(n + 1, true);  
    is_prime[0] = is_prime[1] = false;   
    for (int i = 2; i * i <= n; i++) {   
        if (is_prime[i]) {               
            for (int j = i * i; j <= n; j += i) is_prime[j] = false;
        }
    }
    v primes;  
    loop(i,2,n+1) {
        if (is_prime[i])  primes.push_back(i); 
    }
    return primes;
}
 
int power(int x, int y) {
    if(y == 0) return 1;
    int temp = power(x, y/2);
    if(y%2 == 1) return temp*temp*x;
    else return temp*temp;
}

int modularExponentiation(int x, int y, int p) {
    int res = 1;
    x = x % p;
    if (x == 0){
        if(y==0) return 1;
        else return 0;
    }
    while (y > 0) {
        if (y & 1)
            res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}
 
int nCr(int n, int r) {
    if (r > n) return 0;
    if (r == 0 || r == n) return 1;
    int res = 1;
    r = min(r, n - r);
    for (int i = 0; i < r; i++) {
        res *= (n - i);
        res /= (i + 1);
    }
    return res;
}
 
int NewtonSQRT(int n) {
    int x = n;
    int y = (x + 1) / 2;
    while (y < x) {
        x = y;
        y = (x + n / x) / 2;
    }
    if (x * x == n) return x;
    return -1; 
}

vp factorize(int n) {
    vp fact;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) { 
            int cnt = 0; 
            while (n % i == 0) {
                n /= i;
                cnt++;
            }
            fact.push_back({i, cnt});
        }
    }
    if (n > 1) fact.push_back({n, 1});
    return fact;
}

int mod(int a, int m = MOD) {
    return a % m;
}
 
template <class T> class Math {
  public:
    vector<T> fact, invfact;
    Math() {}
    Math(int n) {
        fact.resize(n);
        invfact.resize(n);
        fact[0] = invfact[0] = 1;
        for (int i = 1; i < n; i++) {
            fact[i] = mod(i * fact[i - 1]);
            invfact[i] = modinv(fact[i]);
        }
    }
    T modinv(T x, T m = MOD) { return expo(x, m - 2, m); }
    T expo(T base, T exp, T m = MOD) {
        T res = 1;
        while (exp) {
            if (exp & 1)
                res = mod(res * base, m);
            base = mod(base * base, m);
            exp >>= 1;
        }
        return res;
    }
    T choose(T n, T k) {
        if (k < 0 || k > n)
            return 0;
        T ans = fact[n];
        ans = mod(ans * invfact[n - k]);
        ans = mod(ans * invfact[k]);
        return ans;
    }
};

int phi(int n){
    vp fact = factorize(n);
    int ans = n;
    loop(i,0,fact.size()) ans -= ans/fact[i].ft;
    return ans;
}

v derangement(int n) {
    v ans;
    ans.push_back(0);
    ans.push_back(0);
    ans.push_back(1);
    loop(i,3,n+1) ans.push_back(((i-1)%MOD)*((ans[i-1]%MOD+ans[i-2]%MOD)%MOD));
    return ans;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>k;
    vector<int> c(n);
    for(int i = 0; i < n; i++) cin>>c[i];
    vector<vector<int>> dp(n+1, vector<int>(k+1));
    for(int i = 0; i < n; i++) dp[i][0] = 1;
    for(int i = n-1; i>=0; i--) {
        for(int j = 1; j <= k; j++) {
            int skip = dp[i+1][j], pick = 0;
            if(c[i]<=j) pick = dp[i][j-c[i]];
            dp[i][j] = (skip+pick)%MOD;
        }
    }
    cout<<dp[0][k]<<endl;
    return 0;
}