ami có một dãy số nguyên dương \(A\) và một số nguyên dương \(k\).

Nhận thấy dãy \(A\) không mang tính nghệ thuật, 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:

• Mỗi một phần tử \(A_i\) đều thuộc một và chỉ một dãy con.
• Các phần tử trong cùng một dãy con phải có cùng giá trị.
• Độ dài một dãy con không vượt quá \(k\).

Các bạn hãy đếm xem có bao nhiêu cách khác nhau để 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.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) là số phần tử của dãy \(A\).

• \(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)\).

• 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.

Output

• 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\).

Scoring

• Subtask \(1\) (\(60\%\) số điểm): \(1 \leq k \leq n \leq 300\).

• Subtask \(2\) (\(15\%\) số điểm): \(1 \leq k \leq n \leq 5000\).

• Subtask \(3\) (\(25\%\) số điểm): \(1 \leq k \leq n \leq 2*10^5\).

Example

4 
1 
2 
3
1
1

1

4 
2
3 
3
3
2

3