Cho mảng ~N~ số nguyên dương và số nguyên ~M~. Hãy đếm số tập con không rỗng của mảng có tổng chia hết cho ~M~.

Kết quả lấy modulo ~10^9 + 7~.

Input

• Dòng đầu gồm hai số nguyên ~N~ và ~M~ (~1 \le N \le 1000~, ~1 \le M \le 1000~).
• Dòng thứ hai gồm ~N~ số nguyên dương ~a_1, a_2, \ldots, a_N~ (~1 \le a_i \le 1000~).

Output

In ra số tập con không rỗng có tổng chia hết cho ~M~, lấy modulo ~10^9 + 7~.

Ví dụ

Input 1

5 5
5 10 15 20 25

Output 1

31

Giải thích 1

Tất cả ~2^5 - 1 = 31~ tập con không rỗng đều có tổng chia hết cho ~5~.

Giới hạn