{"code":"scarray","name":"Dãy Cùng Màu","description":"[user:ami] có một dãy số nguyên dương $A$ và một số nguyên dương $k$.\r\n\r\nNhận thấy dãy $A$ không mang tính nghệ thuật, [user:ami] muốn tách dãy $A$ thành một vài dãy con liên tiếp thoả mãn điều kiện sau:\r\n\r\n- Mỗi một phần tử $A_i$ đều thuộc một và chỉ một dãy con.\r\n- Các phần tử trong cùng một dãy con phải có cùng giá trị.\r\n- Độ dài một dãy con không vượt quá $k$.\r\n\r\nCác bạn hãy đếm xem có bao nhiêu cách khác nhau để [user:ami] có thể chia dãy thoả mãn các điều kiện trên. Hai cách chia gọi là khác nhau nếu tồn tại hai phần tử $i$ và $j$ khác nhau mà chúng ở chung một nhóm trong một cách, nhưng lại khác nhóm ở cách còn lại.\r\n\r\n

Input

\r\n\r\n- Dòng đầu tiên chứa số nguyên dương $n$ là số phần tử của dãy $A$.\r\n\r\n- $n$ dòng tiếp theo, mỗi dòng chứa $1$ số nguyên dương $A_i$ biểu thị một phần tử của dãy $A$ $(1 \\leq a_i \\leq n)$.\r\n\r\n- Dòng cuối cùng chứa số nguyên dương $k$ là số phần tử tối đa trong một nhóm.\r\n\r\n

Output

\r\n\r\n- Hãy in ra số cách chia khác nhau thoả mãn điều kiện trên sau khi chia dư cho $10^9+7$.\r\n\r\n

Scoring

\r\n\r\n\r\n- Subtask $1$ ($60\\%$ số điểm): $1 \\leq k \\leq n \\leq 300$.\r\n\r\n- Subtask $2$ ($15\\%$ số điểm): $1 \\leq k \\leq n \\leq 5000$.\r\n\r\n- Subtask $3$ ($25\\%$ số điểm): $1 \\leq k \\leq n \\leq 2*10^5$.\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 4 \r\n 1 \r\n 2 \r\n 3\r\n 1\r\n 1\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 1\r\n ```\r\n \r\n ??? warning \"Note\"\r\n\r\n Ở ví dụ 1, chỉ có một cách chia duy nhất là [1 | 2 | 3]. \r\n\r\n!!! question \"Test 2\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 4 \r\n 2\r\n 3 \r\n 3\r\n 3\r\n 2\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 3\r\n ```\r\n \r\n ??? warning \"Note\"\r\n\r\n Ở ví dụ 2, các cách chia thoả mãn là [2 | 3 | 3 | 3] , [2 | 3 3 | 3], và [2 | 3 | 3 3].","points":350.0,"partial":false,"time_limit":2.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}