Thầy Hùng giảng dạy bộ môn Tin học tại một trường THPT vùng cao. Hôm nay thầy nhận được \(N\) phần quà với khối lượng lần lượt \(a_1, a_2, \ldots, a_N\) (gam) để chia đều cho \(K\) lớp đang tham gia trại hè. Thầy muốn chia toàn bộ số quà thành đúng \(K\) nhóm (các nhóm không giao nhau) sao cho tổng khối lượng mỗi nhóm đều bằng nhau. Hãy đếm số cách chia khác nhau (coi hai cách là khác nhau nếu tập chỉ số phần quà của một nhóm nào đó khác nhau).

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên dương \(N\) và \(K\) (\(1 \le N \le 20\), \(1 \le K \le 6\)).
• Dòng tiếp theo chứa \(N\) số nguyên dương \(a_1, a_2, \ldots, a_N\) (\(1 \le a_i \le 50\)).

Định dạng đầu ra

• In ra một số nguyên duy nhất là số cách chia khác nhau. Nếu không thể chia, in ra \(0\).

Ví dụ

Input:

6 2
1 1 1 1 1 1

Output:

10

Giải thích: Có \(\binom{6}{3} = 10\) cách chọn \(3\) phần quà để vào nhóm \(1\), nhóm \(2\) nhận các phần quà còn lại.

Ràng buộc

• \(20\%\) số điểm ứng với \(N \le 10\), \(K = 2\).
• \(30\%\) số điểm ứng với \(N \le 15\), \(K \le 3\).
• \(50\%\) số điểm còn lại không có ràng buộc gì thêm.