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:

• Dòng đầu tiên chứa một số nguyên \(k\ (0 \leq k \leq n \leq 10^{6})\);

• Dòng tiếp theo chứa xâu \(S\) có độ dài không quá \(10^{6}\).

Kết quả: Ghi một số nguyên duy nhất là số lượng xâu con chứa đúng \(k\) kí tự \('H'\).

Ví dụ:

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 \leq 10^{6}\);

• Có 30% số test ứng với 30% số điểm của bài thoả mãn \(k \geq 1,\ \ n \leq 100\);

• Có 30% số test ứng với 30% số điểm của bài thoả mãn \(k \geq 1,\ \ 100 < n \leq 1000\);

• Có 30% số test ứng với 30% số điểm của bài thoả mãn \(k \geq 1,\ 1000 < n \leq 10^{6}\).