자전거 점검 구간 고르기

문제

공유 자전거 운영팀은 하나의 길을 따라 놓인 대여소를 점검하려 한다. 대여소에는 길의 시작부터 차례대로 1번부터 N번까지 번호가 붙어 있다. i번 대여소를 점검하는 데에는 작업량 A_i가 필요하다. 작업량은 서로 같을 수 있지만, 번호가 다른 대여소는 서로 다른 점검 장소로 취급한다. 운영팀은 이번 일정에서 정확히 K개의 대여소를 선택해야 한다. 다만 이웃한 두 대여소를 같은 일정에 넣으면 자전거 이동 안내가 겹치므로, 번호의 차이가 1인 두 대여소는 함께 선택할 수 없다. 첫 번째 대여소와 마지막 대여소는 길의 양 끝에 있으므로, 번호의 차이가 1인 경우를 제외하면 이웃한 것으로 취급하지 않는다. 선택한 대여소의 작업량 합은 준비한 작업량 T와 정확히 같아야 한다. 합이 T보다 작거나 큰 선택은 모두 사용할 수 없다. 점검 순서는 선택의 구별 기준이 아니다. 예를 들어 같은 대여소들을 서로 다른 순서로 나열하더라도 하나의 선택으로 센다. 반대로 작업량의 나열이 같더라도 선택한 대여소 번호가 하나라도 다르면 서로 다른 선택이다. 조건을 모두 만족하는 대여소 집합의 개수를 구해야 한다. 운영팀은 가능한 선택을 모두 비교하려 하므로, 아무 선택이나 하나 찾는 것으로는 충분하지 않다. K가 0이면 아무 대여소도 고르지 않는 선택이 하나 존재하며, 그 작업량 합은 0이다. 따라서 이 선택도 다른 선택과 같은 기준으로 검사한다. 가능한 선택이 전혀 없다면 개수는 0이다.

입력

첫째 줄에 정수 N, K, T가 공백으로 주어진다. 1 ≤ N ≤ 24, 0 ≤ K ≤ ⌈N/2⌉, 0 ≤ T ≤ 2400이다.
둘째 줄에 정수 A_1, …, A_N이 공백으로 주어진다. 모든 i에 대해 1 ≤ A_i ≤ 100이다.

출력

조건을 만족하는 선택의 개수를 정수 하나로 출력한다. 가능한 선택이 없으면 0을 출력한다.

5 2 6
1 2 3 4 5

2

1 0 0
7

1

3 2 3
1 1 1

0

출처: Devin.KR 자체 제작