Sinh viên trường Đại học Kỹ thuật hàng không đã thiết kế một robot hỗ trợ quá trình lắp ráp động cơ máy bay.

Quá trình lắp ráp động cơ có ~26~ loại thao tác khác nhau ký hiệu bằng các chữ cái la tinh thường, các thao tác giống nhau được ghi nhận bằng cùng một ký tự.

Robot được sử dụng một lần để hỗ trợ một phần quá trình lắp ráp gồm dãy các thao tác liên tiếp nhau trong toàn quá trình.

Bộ nhớ robot có ~k~ ô, mỗi ô chứa một lệnh. Các lệnh được thực hiện liên tiếp nhau theo trình tự ghi và sau khi thực hiện lệnh thứ ~k~ robot tiếp tục thực hiện lại chương trình từ đầu. Người ta có thể dừng robot ở bất cứ lúc nào. Việc sử dụng robot được coi là có giá trị kinh tế nếu nó được dùng để thực hiện không ít hơn ~k+1~ thao tác.

Ví dụ, quá trình lắp ráp được mô tả bằng xâu zabacaba và ~k = 2~, ta có ~5~ cách sử dụng robot hiệu quả: nạp vào bộ nhớ robot ab và thực hiện các công việc từ ~2~ đến ~4~ (aba), nạp vào bộ nhớ robot ac và thực hiện các công việc từ ~4~ đến ~6~ (aca), nạp vào bộ nhớ robot ab và thực hiện các công việc từ ~6~ đến ~8~ (aba).

Yêu cầu:

Cho xâu độ dài ~n~ mô tả quá trình lắp ráp ~(1 < n \leq 10^5)~. Hãy xác định số cách sử dụng robot hiệu quả.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên ~k~ ~(0 < k < n)~,
• Dòng thứ 2 chứa xâu mô tả quá trình lắp ráp.

Dữ liệu ra

Một số nguyên – số cách sử dụng robot hiệu quả.

Sample Input

2
zabacabab

Sample Output

5

Nguồn: Kỹ thuật lập trình - thầy Nguyễn Thanh Tùng