32175번 - 컵 쌓기

문제

주식회사 푸앙의 추종자인 잇창명은 푸앙에서 생산하는 $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$

힌트