Sau khi chơi với ngọc chán chê, Tí sắp \(n\) viên ngọc ra một đường thẳng và bắt đầu nhìn ngắm chúng. Tí nhận thấy rằng có không quá \(k\) màu ngọc khác nhau trên bàn và viên ngọc thứ \(i\) từ trái sang thì có màu \(a_i\). Tí muốn chia dãy ngọc thành các đoạn liên tiếp sao cho mỗi đoạn đều có đủ \(k\) màu. Hỏi Tí có bao nhiêu cách chia thỏa mãn như vậy?

Yêu cầu: In số cách chia thỏa mãn sau khi \(\mod 10^9+7\)

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n,k\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,...,a_n\).

Output

• Ghi ra một số nguyên là kết quả bài toán.

Constraints

• \(1\leq k\leq n\leq 10^6\)
• \(1\leq a_i\leq k\)

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(k = 1\).
• Subtask \(2\) (\(20\%\) số điểm): \(n\leq 5000\).
• Subtask \(3\) (\(20\%\) số điểm): \(n\leq 10^5, k\leq 100\).
• Subtask \(4\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

5 2
1 2 2 1 2 

3