Problem
Sinh viên từ một trong các trường đại học đã thiết kế rô-bốt để tự động hóa một phần quy trình lắp ráp động cơ máy bay.
Trong quá trình lắp ráp động cơ, có thể xảy ra 26 loại thao tác, được biểu thị bằng các chữ cái viết thường của bảng chữ cái Latinh. Quy trình lắp ráp bao gồm N thao tác.
Được cho là sử dụng robot một lần để thực hiện một phần các thao tác liên tiếp từ quy trình lắp ráp.
Bộ nhớ của robot bao gồm K ô, mỗi ô chứa một thao tác. Các thao tác được thực hiện tuần tự, bắt đầu với thao tác đầu tiên, theo thứ tự chúng được đặt trong bộ nhớ. Sau khi hoàn thành cái cuối cùng, robot tiếp tục với cái đầu tiên. Robot có thể dừng lại sau bất kỳ thao tác nào. Sử dụng rô-bốt là khả thi về mặt kinh tế nếu rô-bốt thực hiện ít nhất K + 1 thao tác.
Bạn cần viết một chương trình, dựa trên quy trình lắp ráp, sẽ xác định số cách hiệu quả về mặt kinh tế để sử dụng rô-bốt.
Đầu vào
Dòng đầu tiên chứa số K > 0 - số thao tác có thể ghi vào bộ nhớ của rô-bốt.
Dòng thứ hai bao gồm N > K chữ cái Latinh viết thường biểu thị hoạt động - quá trình lắp ráp động cơ. Các thao tác cùng loại được biểu thị bằng cùng một chữ cái (N <= 200000).
Đầu ra
In ra một số nguyên - số cách sử dụng rô-bốt tiết kiệm chi phí.
| Đầu vào |
Đầu ra |
|
2
zabacabab
|
5 |
2
abc |
0 |