問題文

長さが $N$ の文字列 $S$ が与えられます。

回文が好きなやきとりくんは、文字列 $S$ の連続する部分列から回文を探そうとしています。
しかし、連続する部分列の中で $2$ 回以上出てくる回文はありきたりな回文なため、好ましくありません。

やきとりくんのために、連続する部分列の中で $1$ 回だけ出てくる回文は何種類あるかを求めてください。

制約

• $1 \leq N \leq 10^5$
• $N$ は整数である。
• $S$ は英小文字からなる文字列

入力

入力は以下の形式で標準入力から与えられる。

出力

問題の答えを一行に出力せよ。

入出力例

8
abbacabd

6

以下の $6$ 種類の回文が条件に該当します。

• abba
• aca
• bacab
• bb
• c
• d