問題

長さ44の文字列 C1C2C3C4C_1C_2C_3C_4 であって C1=C3C_1 = C_3 かつ C2=C4C_2 = C_4 が成り立つものを ABAB\text{ABAB} 文字列とします。 特に C1=C2C_1 = C_2 であっても ABAB\text{ABAB} 文字列です。

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

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

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

制約

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

入力

NN
SS

出力

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

入力例1

7
abadaab

出力例1

4

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

入力例2

6
penpen

出力例2

3

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

提出


Go (1.21)