Chọn Đúng K Món

Có $N$ món hàng phân biệt, món thứ $i$ có giá $a_i$. Hãy đếm số cách chọn đúng $K$ món sao cho tổng giá không vượt quá $P$. Hai cách chọn khác nhau nếu chúng khác nhau ở ít nhất một chỉ số món hàng.

Input

• Dòng đầu chứa ba số nguyên $N,K,P$.
• Dòng thứ hai chứa $N$ số nguyên dương $a_1,a_2,\dots ,a_N$.

Output

• In số tập con gồm đúng $K$ vị trí và có tổng không vượt $P$.

Constraints

• $1\le K\le N\le 40$.
• $1\le P\le 10^{18}$.
• $1\le a_i\le 10^{16}$.

Scoring

• Subtask $1$ ($50\%$ số điểm): $N\le 20$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

5 3 12
2 3 4 5 8

4