Doublindromes

Time limit3sMemory limit512 MB

Summary

Count distinct substrings of s that are palindromes and split into two non-empty palindromes, with length at least k.

Level: Hard9 of 10
Topics: String, String matching, Hash map, Dynamic programming
Solved: No attempts yet

Problem

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

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

Input

The first line 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$ ).

Output

Print one integer: the answer to the problem.

Examples1

Example 1
Input
```
3
xyxxyxxyx
```
Expected output
```
2
```