Dãy ngọc (Chọn ĐT'20-21)

Xem PDF

Điểm: 500 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

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

Test 1

Input
5 2
1 2 2 1 2 
Output
3
Note

Có 3 cách chia như sau: \((1\ 2) | (2\ 1\ 2), (1\ 2\ 2) | (1\ 2)\), hoặc \((1\ 2\ 2\ 1\ 2)\).


Bình luận

Không có bình luận nào.