분식집 사장 도현이는 메뉴 \(N\) 개의 가격을 적어 두었다. \(i\) 번째 메뉴의 가격은 \(a_i\) 이다.

손님이 메뉴를 한 개 이상 골라 주문할 때, 주문한 메뉴 가격의 합이 \(K\) 의 배수가 되면 사은품을 준다. 메뉴를 고르는 비어 있지 않은 부분집합 중 가격 합이 \(K\) 의 배수가 되는 경우의 수를 구하여라.

(서로 다른 메뉴는 가격이 같더라도 다른 것으로 취급한다.)

• \(1 \le N \le 20\)
• \(1 \le K \le 1{,}000\)
• \(1 \le a_i \le 1{,}000{,}000\)

첫째 줄에 메뉴 수 \(N\) 과 정수 \(K\) 가 주어진다.

둘째 줄에 \(N\) 개의 가격 \(a_1, \dots, a_N\) 이 공백으로 구분되어 주어진다.

가격 합이 \(K\) 의 배수가 되는, 비어 있지 않은 부분집합의 개수를 한 줄에 출력한다.

riseoj 작성

출처 Original