#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k, tmp;
cin >> n >> k;
//dp[i] = i원을 만들 경우
//dp[0] = 0원을 만들 경우 = 동전을 선택하지 않는 경우
int dp[k+1] = {1};
for (int i = 0; i < n; i++) {
cin >> tmp;
for (int j = 0; j <= k-tmp; j++) {
dp[j+tmp] += dp[j];
}
}
cout << dp[k];
return 0;
}
output : k원을 만드는 경우의 수
dp[i]
: i원을 만드는 경우의 수
dp[0]
: 아무 동전을 선택하지 않는 경우
dp[0]
= 1
1원에 대해서 dp[i] += dp[i-1]
2원에 대해서 dp[i] += dp[i-2]
5원에 대해서 dp[i] += dp[i-5]
output : dp[k]