Trong lá thư gửi cho người tình bé nhỏ Dao Ánh sau bao tháng ngày xa cách, cố nhạc sỹ Trịnh Công Sơn đã thể hiện niềm nhớ thương da diết qua từng nét chữ:

“…Anh hát lại bản Mưa Hồng mà anh đã viết cho những ngày tháng Ánh giận anh ở Huế. Bản nhạc hát lại bỗng thấy buồn hơn. Có lẽ Ánh chưa nghe bản ấy vì từ dạo đó về sau anh chỉ gặp Ánh một hai lần gì đó rất ngắn và bặt tăm luôn. Có lẽ anh sẽ đổi lại đầu đề Tuổi đá buồn. Ánh nghĩ sao? Ánh có giận gì anh mà lâu thế anh không được tin. Hãy viết thư cho anh dù rất ngắn cũng được. Anh mong lắm”.

Tất cả như chất chứa nỗi lòng của người nghệ sỹ, và cũng nói lên hoàn cảnh ra đời bài hát nổi tiếng "Mưa Hồng".

Hôm nay có cơn mưa mùa Hạ nặng hạt trên toàn địa bàn thành phố Tam Kỳ, làm dịu đi cái nắng hè oi bức. Trí và Huy vừa cùng nhau luyện đề Pre-QNOI, vừa đắm chìm trong giai điệu bài hát Mưa Hồng, còn gì tuyệt bằng. Bỗng từ trên tivi phát sóng bản tin thời tiết, biên tập viên thông báo mức độ nước mưa của từng khu vực trong thành phố. Các khu vực được đánh số theo thứ tự từ \(1\) đến \(n\), nằm liên tiếp nhau. Huy chợt nảy ra ý tưởng cho một bài toán mới và đố Trí.

Bài toán được phát biểu như sau: Đếm số lượng tập hợp các khu vực (không cần liên tiếp nhau, nhưng không được thay đổi thứ tự), sao cho khi xét riêng những khu vực đó, hai khu vực liên tiếp nhau trong đó luôn có tổng lượng mưa không chia hết cho số nguyên dương \(k\).

Vì vẫn chưa dứt được tâm hồn khỏi giai điệu bài hát, nên Trí không thể toàn tâm toàn ý suy nghĩ hướng giải cho bài toán này được. Các bạn hãy giúp Trí nhé!

Input

• Dòng đầu chứa \(2\) số nguyên dương \(n\) và \(k\);
• Dòng thứ hai chứa \(n\) số nguyên dương \(r_i\ (\leq10^{18})\) thể hiện mực nước mưa ở từng khu vực.

Output

• In ra một số nguyên dương duy nhất, là số tập thỏa yêu cầu bài toán. Vì kết quả có thể rất lớn nên chỉ cần in ra phần dư của nó khi chia cho \(10^9+7\).

Ví dụ

Sample input

4 5
16 3 4 7

Sample output

11

Notes

• Có \(11\) tập thỏa yêu cầu bài toán: \((16),\ (3),\ (4),\ (7),\ (16,\ 3),\ (16,\ 7),\ (3,\ 4),\ (4, 7),\ (16,\ 3,\ 4),\ (3,\ 4,\ 7),\ (16,\ 3,\ 4,\ 7)\).
• Tập \((16,\ 4)\) không thỏa vì có \((16+4)\ \vdots\ 5\); tập \((16,\ 3,\ 7)\) không thỏa vì có \((3+7)\ \vdots\ 5\); tập \((16,\ 4,\ 7)\) không thỏa vì có \((16+4)\ \vdots\ 5\); \(\ldots\)

Ràng buộc

• Có \(20\%\) test tương ứng với \(20\%\) số điểm của bài có \(n\leq20,\ k\leq10^6\);
• Có \(20\%\) test khác tương ứng với \(20\%\) số điểm của bài có \(n\leq10^3,\ k\leq10^6\);
• Có \(20\%\) test khác tương ứng với \(20\%\) số điểm của bài có \(n\leq10^6,\ k\leq100\);
• Có \(20\%\) test khác tương ứng với \(20\%\) số điểm của bài có \(n\leq10^6,\ k\leq10^6\);
• Có \(20\%\) test còn lại tương ứng với \(20\%\) số điểm của bài có \(n\leq10^6,\ k\leq10^{18}\).