問題


長さの文字列 であって かつ が成り立つものを 文字列とします。 特に であっても 文字列です。

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

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

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

制約


  • は全て英小文字からなる文字列
  • は整数

入力



出力


答えを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.14)