Au4B - Troco de moedinhas

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

const int N = 2002;
ll mo = 1e9; //mod que vai ser tirado
ll dp[N][N]; //criando dp pra salvar os dados
int v[N];
int n;

ll f(int T, int m){
	if (T == 0) return 1LL;
	if (T < 0 or n == m) return 0LL;
	if (dp[T][m] != -1) return dp[T][m]; //já foi feita? dp

	ll res = f(T,m+1); //função recursiva
	res = (res + f (T- v[m],m))%mo; //função recursiva, tirando mod
	return dp[T][m] = res; //salvando (dp)
}
int main(){
	int t;
	cin >> n >> t; //nro de moedas e troco que deseja obter
	for (int i=0; i<n; ++i){
		cin >> v[i]; //ler valores
	}
	memset (dp, -1, sizeof dp); //setando dp
	cout << f(t,0) << endl;
	return 0;
}