样例全过，代码全错(也不算吧，30分)

#include<bits/stdc++.h>
using namespace std;
int m,n,s[114514],ans,k;
long long dp[114514];
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>s[i];
	}
	dp[0]=1;
	for(int i=1;i<=m;i++){
		k = 1e9;
		for(int j=1;j<=n;j++){
			if(i>=s[j]){
				dp[i]=(dp[i]+dp[i-s[j]])%k;
			}
		} 
//		cout<<"dp[" << i << "] = " << dp[i] <<endl;
	}
	cout<<dp[m]%k;
	return 0;
}