题目描述

对于一个长度为 $N$ 的字符串 $S$，我们称字符串 $S_0S_1S_2\ldots S_i$ 为字符串的一个前缀，称字符串 $S_iS_{i+1}S_{i+2}\ldots S_{n-1}$ 为字符串的一个后缀。

border 这个东西是字符串中的一个很有趣的概念，你可以在各种字符串算法中见到它。

若字符串 $S$ 存在一个前缀 $S_0S_1S_2\ldots S_{k−1}$ 与后缀 $S_{n-k}S_{n-k+1}S_{n-k+2}\ldots S_{n-1}$ 完全匹配，则称 $S$ 有一个长度大小为 $k$ 的 border。

一般来讲，border 是不包括自身的，因为研究字符串问题时一般都是关注子串，所以我们定义 border 不能完全匹配自身，即一个长度为 $N$ 的字符串虽然有一个长度大小为 $N$ 的前缀和后缀完全匹配，我们也不认为这是一个合法的 border。

对于一个字符串 $S$，牛牛还定义了它的 border val，所谓 border val 就是指字符串中所有 border 的长度总和。

例如字符串 abacaba 的 border val 就是 $1+3=4$。（它有一个长度大小为 $3$ 的 border aba 和一个长度大小为 $1$ 的 border a。）

我们称一个字符串中连续的一段为字符串的一个子串，一个长度大小为 $N$ 的字符串有 $N\times (N − 1)/2$ 个子串。

现在给定一个字符串 $S$，牛牛想要知道所有子串的 border val 之和是多少。

输入格式

第一行输入一个正整数 $N$，表示字符串的长度。

接下来一行输入一个长度为 $N$ 的字符串 $S$，$S$ 串仅包含小写英文字母。

输出格式

仅一个整数，表示所有子串的 border val 之和。

样例

4
aaaa

15

52
ababababababababccdwjkodflksnvlkjwsdlaqsabababababab

3727

数据范围

• 对于前 $20\%$ 的测试数据，保证 $N \le 100$。
• 对于前 $30\%$ 的测试数据，保证 $N \le 3\times 10^3$。
• 对于另 $10\%$ 的测试数据，保证字符串仅有小写英文字母 a 组成。
• 对于另 $10\%$ 的测试数据，保证字符串完全随机。
• 对于另 $100\%$ 的测试数据，保证 $1 \le N \le 10^5$ 字符串仅包括小写英文字母。