Bobo có một dãy gồm \(N\) số nguyên \(a_1, a_2, \dots, a_N\) và một số nguyên K. Bobo muốn đếm xem có bao nhiêu tập con (kể cả tập rỗng) mà tổng các phần tử chia hết cho \(K\).

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

• Dòng 1: Hai số nguyên \(N\) và K (\(1 \le N \le 20, 1 \le K $\le 10^9\)).
• Dòng 2: \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(1 \le a_i $\le 10^9\)).

Định dạng đầu ra

• In ra số lượng tập con có tổng chia hết cho \(K\).

Ví dụ

Input:

3 2
1 2 3

Output:

4

Giải thích: Các tập con có tổng chẵn (chia hết cho 2) gồm: \(\emptyset\) (tổng 0), \(\{2\}\) (tổng 2), \(\{1, 3\}\) (tổng 4), \(\{1, 2, 3\}\) (tổng 6). Tổng cộng 4 tập con.

Ràng buộc & Subtasks