Shared code

/* ~~Abhimanyu Kadhane~~ */
#include <bits/stdc++.h>
#define ll long long
#define all(x) (x).begin(),(x).end()  
#define allr(x) (x).rbegin(),(x).rend()   
#define M 1000000007
#define int long long
using namespace std;

long long  change(int amount, vector<int>& coins) {
    int n=coins.size();
    vector<int>prevdp(amount+1);
    vector<int>currdp(amount+1);
    prevdp[0]=currdp[0]=1;
    for(int i=1; i<=amount; i++)if(i%coins[0]==0)prevdp[i]++;
    for(int ind=1; ind<n; ind++){
        for(int x=0; x<=amount; x++){
            long long  noTake=prevdp[x];
            long long  take=0;
            if(x>=coins[ind])take=currdp[x-coins[ind]];
            currdp[x]=(take+noTake)%M;
        }
        prevdp=currdp;
    }
    return prevdp[amount];
}

void solve(){
   int n,x;cin>>n>>x;
   vector<int>v(n);
   for(auto &i:v)cin>>i;   
   cout<<change(x,v); 
}

signed main(){
    
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  
  int tt;
  tt=1;
  // cin >> tt;
   
  while (tt--)solve();
  
  return 0;
  
}