Cho xâu \(S\) và số nguyên \(K\). Đếm số palindrome con trong xâu \(S\) có độ dài chính xác bằng \(K\).

Định dạng đầu vào

• Một dòng chứa xâu \(S\) (\(1 \le |S| \le 10^5\)).
• Một số nguyên \(K\) (\(1 \le K \le |S|\)).

Định dạng đầu ra

• Một số nguyên là số palindrome con có độ dài đúng bằng \(K\).

Ví dụ

Input:

abacaba
3

Output:

3

Giải thích: Các palindrome độ dài 3: aba (vị trí 0), aca (vị trí 2), aba (vị trí 4).

Ràng buộc

• 50% số điểm: \(|S| \le 1000\).
• 50% số điểm còn lại: \(|S| \le 10^5\).