Link to this code: https://cses.fi/paste/6e7d481ced00cb5a285d3d/
#include<iostream>

#include<vector>

using namespace std;

#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

int distinct_ways(vector<int>&coins,vector<vector<int>>&cache,int sum,int n)
{

  if(cache[sum][n]!=-1)
  {
    return cache[sum][n];
  } 

  if(sum==0)
  {
    return cache[sum][n]=1;
  }

  if(sum<0) 
  {
    return cache[sum][n]=0;
  }

  if(n<=0)
  {
    return cache[sum][n]=0; 
  } 

  if(sum-coins[n-1]>=0)
  {
    return cache[sum][n]=(distinct_ways(coins,cache,sum-coins[n-1],n)
      +distinct_ways(coins,cache,sum,n-1))%1000000007;
  }

  else
  {
    return cache[sum][n]=distinct_ways(coins,cache,sum,n-1)%1000000007;
  }  

}

void solve()
{
  int n,sum;
  cin>>n>>sum;

  vector<int>coins(n);
  vector<vector<int>>cache(sum+1,vector<int>(n+1,-1));

  for(int&i:coins)
  {
    cin>>i;
  }

  cout<<distinct_ways(coins,cache,sum,n);

}

int main() 
{
  fastio();  
  solve();
  return 0;
}