ABAB

問題

長さ$4$の文字列 $C_1C_2C_3C_4$ であって $C_1 = C_3$ かつ $C_2 = C_4$ が成り立つものを $\text{ABAB}$ 文字列とします。 特に $C_1 = C_2$ であっても $\text{ABAB}$ 文字列です。

長さ $N$ の英小文字からなる文字列 $S$ が与えられます。$S$ の長さ4の部分列であって、$\text{ABAB}$ 文字列であるものはいくつありますか？

ただし、文字列として同じであっても取り出す位置が違えば違うものとして扱います。

$S$ の部分列とは、$S$ からいくつかの文字を取り出して、それらを元の順序を保って並べた新しい文字列のことを指します。

制約

• $1 \leqq N \leqq 10^3$
• $|S| = N$
• $S$ は全て英小文字からなる文字列
• $N$ は整数

入力

出力

答えを１行に出力してください。

入力例１

7
abadaab

出力例１

4

ababとaaaaがあります。ただし、ababは取り出す位置が(1,2,5,7),(1,2,6,7),(2,3,4,7)の３種類がありこれは異なるものとして数えるので合計４通りです。

入力例２

6
penpen

出力例２

3

pepe,enen,pnpnの３種類です。