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

Vì \(N\) nhỏ (\(N \le 20\)), Bobo có thể dùng bitmask duyệt toàn bộ \(2^N\) tập con.

Input:

• Dòng 1: \(N\) và \(K\) (\(1 \le N \le 20\), \(1 \le K \le 10^9\))
• Dòng 2: \(N\) số nguyên \(a_i\) (\(1 \le a_i \le 10^9\))

Output: Một số nguyên — số tập con có tổng chia hết cho \(K\) (kể cả tập rỗng).

Ví dụ: Input:

3 2
1 2 3

Output:

4

Giải thích: Các tập con có tổng chẵn gồm {}, {2}, {1,3}, {1,2,3}.