Cô Q là 1 người yêu thích về tập hợp nên cô giao cho các bạn sinh viên 1 bài tập như sau.

Cho dãy n phần tử a₁, a₂, ... a_n và số nguyên k. Hãy đếm xem có bao nhiêu tập hợp con khác rỗng sao cho tổng các phần tử của tập hợp con chia hết cho k.

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên n và k.
• Dòng tiếp theo chứa n số tự nhiên a₁, a₂, ... a_n.

Dữ liệu ra:

• 1 dòng chứa số lượng tập hợp con khác rỗng sao cho tổng các phần tử của chúng chia hết cho k.

Input:

3 2
1 2 3

Output:

3

Giải thích:

• Có 3 tập hợp con {2}, {1, 3}, {1, 2, 3} thỏa mãn.

Giới hạn:

• ~1 \le n \le 20~, ~2 \le k \le 100~.
• ~1 \le a_i \le 10^{6}~.