수집가 하늘이는 서로 무게가 적힌 \(N\) 개의 동전을 가지고 있다. \(i\) 번째 동전의 무게는 \(w_i\) 이다.

동전들 중 일부(공집합 포함)를 골라 그 무게 합이 정확히 \(S\) 가 되게 하는 서로 다른 선택 방법의 수를 구하려고 한다. 두 동전이 무게가 같더라도 서로 다른 동전으로 취급한다.

방법의 수는 매우 클 수 있으므로 \(1{,}000{,}000{,}007\) 로 나눈 나머지를 출력하여라.

• \(1 \le N \le 200\)
• \(0 \le S \le 50{,}000\)
• \(1 \le w_i \le 1{,}000\)

첫째 줄에 동전의 수 \(N\) 과 목표 무게 \(S\) 가 주어진다.

둘째 줄에 \(N\) 개의 동전 무게 \(w_1, w_2, \dots, w_N\) 이 공백으로 구분되어 주어진다.

무게 합이 정확히 \(S\) 가 되는 선택 방법의 수를 \(1{,}000{,}000{,}007\) 로 나눈 나머지를 한 줄에 출력한다.

riseoj 작성

출처 Original