Hai chị em dinhkhanhha_ và dth đang chơi một trò chơi với xâu. dinhkhanhha_ sẽ chọn một xâu \(s\) với độ dài \(n\). Sau đó dth sẽ chọn ra \(k\) xâu con† của \(s\). Vì đã giống nhau sẵn nên lúc nào hai chị họ cũng muốn những điều khác biệt. Hãy giúp dth chọn sao cho số lượng xâu con phân biệt là tối đa.

†Xâu \(a\) được gọi là xâu con của xâu \(b\) nếu ta có thể thu được xâu \(a\) sau khi xoá một hoặc một vài (có thể không xoá) kí tự ở đầu và ở cuối của xâu \(b\).

Input

• Dòng đầu tiên nhập vào hai số nguyên dương \(n\), \(k\) - độ dài của xâu \(s\) và số xâu con cần chọn.
• Dòng tiếp theo, nhập vào một xâu \(s\) chỉ bao gồm các kí tự latin in thường.

Output

• Gồm một số nguyên dương duy nhất là kết quả của bài toán.

Example

3 7
aba

5

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n \leq 100\), \(k \le 10^{18}\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \leq 10^5\), \(k \le 10^{18}\). Xâu \(s\) chỉ gồm \(1\) loại kí tự.
• Subtask \(3\) (\(30\%\) số điểm): \(n \le 10^3\), \(k \le 10^{18}\).