시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 0 0 0 0.000%

문제

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.

예제 입력 1

3
xyxxyxxyx

예제 출력 1

2