Cho một dãy gồm ~N~ số nguyên ~a_1, a_2, \dots, a_N~ và một số nguyên dương ~K~. Ta có biểu thức: ~? a_1 ? a_2 \dots ? a_N = X~ Trong đó ta có thể thay thế dấu ‘?’ bằng các phép toán ‘+’ hoặc ‘-’. Hãy đếm xem có tất cả bao nhiêu cách thay dấu khác nhau để ~X~ chia hết cho ~K~. Hai cách thay dấu gọi là khác nhau nếu tồn tại một vị trí mà ở đó dấu ở cách này khác dấu ở cách kia.

Yêu cầu: Đếm số cách thay dấu sao cho kết quả chia hết cho ~K~, lấy modulo cho ~10^9 + 7~.

Input

• Dòng đầu tiên gồm 2 số nguyên dương ~N, K~.
• Dòng thứ hai gồm ~N~ số nguyên dương ~a_1, a_2, \dots, a_N~ (~a_i \le 10^9~).

Output

• Ghi ra số cách thay dấu lấy modulo cho ~10^9 + 7~.