19032번 - Doublindromes 다국어

A string $a$ is a doublindrome if it is a palindrome and it can be represented as concatenation of two non-empty palindromes $b$ and $c$.

Given a string $s$ composed of lowercase English letters, you must find the number of distinct substrings in $s$ which are doublindromes of length $k$ or more. Two substrings are considered distinct if they differ as strings.

The first line of the input contains one integer $k$ ($2 \le k \le 10^4$). The second line contains the string $s$ consisting of lowercase English letters ($k \le |s| \le 10^4$).

Print one integer: the answer to the problem.