1)
dp[x]: 현재까지 고려한 동전으로x원을 만드는 조합(순서무시)의 개수
2) 초기값:dp[0] = 1(아무 동전도 안 쓰는 1가지 경우)
3) 루프 순서: 동전 바깥, 금액 오름차순 (조합 + 무한사용)
4) 점화식 :dp[value] += dp[value - c]는 마지막에 동전c를 하나 더 쓴 경우(동전 c를 쓰기 위해 value - c한 경우의 수)를 누적함
n, k = map(int, input().split())
coins = []
for i in range(n):
line = int(input())
coins.append(line)
# dp[x] : 현재까지 고려한 동전들로 x원을 만드는 조합의 개수
dp = [0] * (k + 1)
dp[0] = 1
# 순서가 상관없는 경우(조합)에는 동전 루프를 바깥 루프로 (순서 상관있는 경우에는 동전 루프를 안쪽 루프로)
for c in coins:
# 값은 오름차순으로 해야 무한 사용 가능! (내림차순 = 중복 안될때)
for value in range(c, k + 1):
dp[value] += dp[value - c]
print(dp[k])
