Tại một khu vườn rực rỡ sắc màu, có rất nhiều loài hoa khác nhau. Mỗi ngày, Luna phải chăm sóc các bông hoa và tạo ra những bó hoa để tặng cho du khách. Một hôm, Luna nhận được một đơn hàng đặc biệt từ một nhóm khách du lịch. Họ muốn có một bộ sưu tập các bó hoa, nhưng mỗi bó hoa không được có quá k loài hoa khác nhau. Luna có ~n~ bông hoa, hoa thứ ~i~ thuộc loại ~c_i~. Luna phải chia ~n~ bông hoa này thành nhiều bó hoa (đoạn) liên tiếp thỏa mãn yêu cầu của khách du lịch. Bạn hãy giúp Luna đếm xem có bao nhiêu cách nhé!

Ví dụ: ~c~ = [1, 2, 3], ~n~ = 3, ~k~ = 2. Có 3 cách chia thỏa mãn: [1] [2] [3] và [1, 2] [3] và [1] [2, 3]

Input

Dòng đầu tiên gồm ~n~ và ~k(1 ≤ k ≤ n ≤ 105)~, với ~n~ là số lượng bông hoa, ~k~ là số lượng loại hoa tối đa khác nhau trong một bó hoa.

Dòng thứ hai gồm ~n~ giá trị ~c_1, c_2, ..., c_n (1 ≤ c_i ≤ n)~ là loại hoa của bông hoa thứ ~i~.

Output

Một dòng duy nhất là kết quả của bài toán. Hãy in kết quả ~MOD 109 + 7~.

Note

Ví dụ là kết quả của đề bài

Subtask

• Subtask 1 (70 điểm): ~n ≤ 10^3~
• Subtask 2 (30 điểm): Không giới hạn gì thêm

Sample Input 1

3 2
1 2 3

Sample Ouput 1

3