보관함에서 만드는 정시 재생목록

문제

음악 스트리밍 서비스에서 사용자가 보관함의 곡을 골라 정해진 시간에 끝나는 재생목록을 만들려고 한다. 보관함에는 N개의 곡이 있으며, 각 곡에는 등록된 순서대로 1번부터 N번까지 번호가 붙어 있다. i번 곡의 재생 시간은 A_i초다. 재생 시간은 모두 양의 정수이며, 곡 사이에 대기 시간이나 별도의 안내 음성은 없다. 사용자는 정확히 K개의 곡을 선택하고, 선택한 곡의 재생 시간 합을 정확히 T초로 맞추려 한다. 각 곡은 선택하지 않거나 한 번만 선택할 수 있다. 곡의 일부만 재생하거나 재생 속도를 바꾸는 것은 허용하지 않는다. 따라서 선택한 곡들의 재생 시간을 그대로 더한 값이 재생목록의 전체 길이가 된다. 선택한 곡은 반드시 보관함의 번호가 작은 순서대로 재생한다. 사용자가 곡의 순서를 따로 바꾸는 경우는 세지 않는다. 두 재생목록에서 선택한 곡 번호의 집합이 다르면 서로 다른 재생목록이다. 재생 시간이 같은 곡이라도 번호가 다르면 별개의 곡이므로, 어느 번호를 골랐는지에 따라 서로 다른 재생목록이 될 수 있다. 반대로 선택한 번호가 모두 같다면 같은 재생목록이다. K가 0일 수도 있다. 이때 선택한 곡이 없는 빈 재생목록의 전체 길이는 0초이며, 빈 재생목록은 하나만 존재한다. 곡을 하나라도 선택하면 전체 길이는 양수다. 목표 시간에 가까운 재생목록이나 곡 수가 다른 재생목록은 조건을 만족하지 않는다. 보관함의 정보와 K, T가 주어질 때, 두 조건을 모두 만족하는 서로 다른 재생목록의 개수를 구한다. 가능한 재생목록을 직접 출력할 필요는 없으며, 조건을 만족하는 재생목록이 하나도 없으면 개수는 0이다.

입력

첫째 줄에 정수 N, K, T가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 20, 0 ≤ K ≤ N, 0 ≤ T ≤ 20,000,000이다.
둘째 줄에 각 곡의 재생 시간 A_1, A_2, …, A_N이 공백으로 구분되어 주어진다. 모든 A_i는 정수이며 1 ≤ A_i ≤ 1,000,000이다.

출력

정확히 K개의 곡을 선택하고 재생 시간 합이 정확히 T초인 서로 다른 재생목록의 개수를 정수 하나로 출력한다. 조건을 만족하는 재생목록이 없으면 0을 출력한다.

5 2 5
2 3 2 5 3

4

3 0 0
8 8 8

1

4 2 7
4 4 4 4

0

출처: Devin.KR 자체 제작