Sưu tập tiền xu

Nam có một bộ sưu tập \(N\) đồng tiền có giá trị \(T_1, T_2, \dots, T_N\). Anh ta muốn chọn ra một tập con các đồng tiền sao cho tổng giá trị của chúng chia hết cho một số \(K\) cho trước. Hãy sử dụng đệ quy để đếm số lượng tập con khác nhau thỏa mãn điều kiện này.

Định nghĩa tập con.
Giả sử \(A = \{1,2,\ldots,N\}\) là tập chỉ số các đồng tiền.
Một tập con \(B\) của \(A\) có thể được viết dưới dạng
$
B = { i_1, i_2, \ldots, i_k }, \; 1 \le i_1 < i_2 < \cdots < i_k \le N.
$
Hai tập con được coi là khác nhau nếu chúng khác nhau về ít nhất một chỉ số.
Tập tất cả các tập con của \(A\) được gọi là lũy thừa của \(A\), ký hiệu \(\mathcal{P}(A)\).
Số lượng tập con của \(A\) là \(2^N\).

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\) (\(1 \leq N \leq 20\), \(1 \leq K \leq 100\)).
• Dòng thứ hai chứa \(N\) số nguyên \(T_1, T_2, \dots, T_N\) (\(1 \leq T_i \leq 10^5\)).

Output

Một số nguyên duy nhất là số lượng tập con có tổng giá trị chia hết cho \(K\).

Example

5 3
2 4 3 4 5

So luong tap con co tong chia het cho 3: 12