"Trick or Treat" - "Cho kẹo hay bị ghẹo", một phong tục không thể thiếu và cũng là hoạt động được trẻ em mong chờ nhất trong dịp Halloween. Trẻ em được hóa trang thành siêu nhân, công chúa hay các nhân vật kinh dị, rồi đi xin kẹo trong ngày Halloween.

Buổi tối Halloween, ~K~ đứa trẻ đã đến gõ cửa xin kẹo nhà ông Phú. Ông Phú đã chuẩn bị ~N~ gói kẹo, mỗi gói có chứa ~a_i~ viên kẹo. Ông cần phải lấy một số gói kẹo cho ~K~ đứa trẻ sao cho tổng số viên kẹo có thể chia đều cho ~K~ đứa. Bạn hãy tính xem có bao nhiêu cách lấy số gói kẹo thỏa mãn.

Dữ liệu vào: Đọc ở file văn bản TRICK.INP:

Dòng đầu chứa số nguyên dương ~N~ và ~K~.

Dòng tiếp theo chứa N số nguyên dương ~a_i~ tương ứng số kẹo trong gói kẹo thứ ~i~.

Dữ liệu ra: Ghi ra file văn bản TRICK.OUT một số duy nhất là số cách cần tìm sau khi chia lấy dư cho ~10^9+7~.

Giới hạn: ~1≤N≤10^3; 1≤K≤10^4 1≤a_i≤ 10^6~

Ví dụ:

TRICK.INP

4 5   
2 
1 
3 
2

TRICK.OUT

3

Giải thích:

Có 3 cách chọn {2,3}; {3,2} và {2,1,2}