2293.py

'''
  풀이
    동적 프로그래밍을 이용하여 풀었다.
    주어진 각 코인에 대해 1 ~ k까지 가능한 경우의 수를 누적시켜 dp테이블을 구한 후 k일 때의 값을 출력하면 된다.
    예를 들어
    주어진 코인이 1, 2, 5라 할 때 k = 10이라 하면 다음과 같은 dp테이블이 만들어진다.
    (편의상 0이 되는 경우의 수를 포함시켜주었다.)
      k     0 1 2 3 4 5 6 7 8 9 10
    coin  1 1 1 1 1 1 1 1 1 1 1 1
          2 1 1 2 2 3 3 4 4 5 5 6
          5 1 1 2 2 3 4 5 6 7 8 10
    먼저, 코인 1로는 모든 k를 만들 수 있으므로 각 k에 대해 1가지 경우의 수가 존재한다.
    그럼, 코인이 2일 때를 생각해보자.
      코인이 2일 때는 해당하는 k에서 "코인 1로 만들 수 있는 경우의 수" + "k - 2일 때의 경우의 수"가 된다.
      (여기서, k - 2일 때의 경우의 수를 더해주는 이유는 간단히 "k - 현재 코인"한 수를 만들 수 있는 경우에 각각 현재 코인 2를 추가하면 코인 2로 k를 만드는 경우가 되기 때문)
    
    좀 더 일반화하여 점화식을 세워보면
    우선, 코인 i을 사용하여 k를 만들 수 있는 경우의 수를 C(i, k)라 정의하자.
    그럼, 코인 n을 사용하여 k를 만들 수 있는 경우의 수 C(n, k)에 대한 점화식은 다음과 같다.
      C(n, k) = C(n - 1, k)               (if. k - n < 0)
                C(n - 1, k) + C(n, k - n) (if. k - n >= 0)
      (여기서, n - 1은 코인 n 이전에 사용한 코인을 의미.)
    이제, 위 점화식을 이용해 dp테이블을 생성한 후 k일 때의 경우의 수를 출력하면 된다.
    단, 해당 문제에서 메모리 제한이 4MB로 팍팍했기 때문에 모든 코인에 대한 dp테이블을 만들지 않았고,
    0 ~ k까지의 1차원 리스트에 값을 갱신하는 방식으로 풀이했다.
'''

import sys
input = lambda: sys.stdin.readline().strip()

def solution():
  n, k = map(int, input().split())
  coins = [int(input()) for _ in range(n)]
  case = [0] * (k + 1)
  case[0] = 1
  
  for c in coins:
    for i in range(1, k + 1):
      case[i] = case[i] + (0 if i - c < 0 else case[i - c])

  print(case[k])

if __name__ == "__main__":
  solution()