컵 쌓기

면접 대비

시간 제한1초메모리 제한1024 MB

요약

각 종류의 컵을 무제한으로 쓸 수 있을 때, 높이 합이 정확히 H가 되는 쌓는 방법의 수를 10^9+7로 나눈 나머지로 구합니다.

난이도: 쉬움10점 중 3점
유형: 동적 계획법
정답자: 아직 제출이 없습니다

문제

주식회사 푸앙의 추종자 잇창명은 푸앙에서 생산하는 $N$ 종류의 컵을 가지고 있다. 이 회사의 컵은 정리하기 쉽도록 종류에 상관없이 입구 사이에 빈틈이 없게 포개어진다. 이 문제에서는 컵의 몸통을 제외하고 입구 부분만 생각한다.

잇창명은 가지고 있는 컵을 포개어 정리하다가, 입구 부분 높이의 합이 $H$ 가 되도록 컵을 포갤 수 있는 경우의 수가 궁금해졌다. 각 종류의 컵은 무한히 많이 있으며, 각 종류 컵의 입구 높이는 단위 높이 $1$ 의 양의 정수배이다. 컵은 입구가 위로 오도록 포갠다.

아래 그림처럼 입구 높이가 각각 $1$ , $1$ , $2$ , $3$ 인 컵 세트를 사용하는 경우를 보자.

위 네 종류의 컵으로 입구 부분의 높이가 $10$ 이 되도록 쌓는 방법은 아래 그림 말고도 여러 가지가 있으며, 모든 경우의 수를 합하면 $9\,003$ 가지이다.

잇창명을 위해 컵을 포개는 경우의 수를 구하는 프로그램을 작성하라.

입력

첫 번째 줄에 $N$ 과 $H$ 가 주어진다.

두 번째 줄에 $N$ 종류의 컵의 높이 $A_1$ , $A_2$ , $A_3$ , $\cdots$ , $A_N$ 이 공백으로 구분되어 주어진다.

출력

입구 부분의 높이 합이 정확히 $H$ 가 되도록 컵을 포개는 경우의 수를 $1\,000\,000\,007$ ( $= 10^9+7$ )로 나눈 나머지를 출력한다.

제한

$1 \le N \le 100$
$1 \le H \le 100\,000$ , $H$ 는 정수
$1 \le A_i \le 100$
$1 \le i \le N$

예제3

예제 1
입력
```
2 3
1 2
```
예상 출력
```
3
```
예제 2
입력
```
4 10
1 1 2 3
```
예상 출력
```
9003
```
예제 3
입력
```
2 100
1 1
```
예상 출력
```
976371285
```