Problem Statement

You are given a string $S$ of length $N$. For each $1\leq i\leq N$, let $S_i$ denote the string obtained by deleting the $i$-th character from $S$.

Find the number of pairs of integers $(i,j)$ that satisfy both of the conditions below.

• $1\leq i < j\leq N$
• $S_i = S_j$

Constraints

• $2\leq N\leq 3\times 10^5$
• $S$ is a string of length $N$ consisting of lowercase English letters.

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the answer.