Xâu TH là xâu có độ dài không quá 10^6, khác rỗng và chỉ chứa hai ký tự 'T' hoặc 'H'. Xâu S1 gọi là xâu con của xâu S2 nếu xâu S1 có độ dài khác 0 và gồm các ký tự liên tiếp trong xâu S2. Ví dụ: xâu "THT" có các xâu con là "T","H","T","TH","HT","THT".

Yêu cầu: Cho S là xâu TH có độ dài n và số nguyên k. Hãy tính số lượng xâu con của S chứa đúng k ký tự 'H'.

Dữ liệu: Vào từ tệp văn bản STRING.INP gồm:

• Dòng đầu tiên chứa một số nguyên k (0≤k≤n≤10^6);
• Dòng tiếp theo chứa xâu S có độ dài không quá 10^6.

Kết quả: Ghi ra tệp văn bản STRING.OUT gồm một số nguyên duy nhất là số lượng xâu con chứa đúng k kí tự 'H'.

Ví dụ:

STRING.INP      STRING.OUT
2               6
THTHTH

Ràng buộc:

Có 10% số test ứng với 10% số điểm của bài thoả mãn k=0,n≤10^6;
Có 30% số test ứng với 30% số điểm của bài thoả mãn k≥1,n≤100;
Có 30% số test ứng với 30% số điểm của bài thoả mãn k≥1,100<n≤1000;
Có 30% số test ứng với 30% số điểm của bài thoả mãn k≥1,1000<n≤10^6.