003 - ハッピー文字列YDK

問題

長さ$N$の文字列$S$があります。
YDKくんは、文字列$S$から以下のような手順で新たな文字列$T$を作成しています。

1.$1 \le i < j < k \le N$となるような三つの整数($i$,$j$,$k$)を決める。
2.$S$の$i$番目の文字と$j$番目の文字と$k$番目の文字をこの順に結合し、それを$T$とする。

YDKくんは、作成した文字列$T$が"YDK"となっているときハッピーになります。
YDKくんがハッピーになるような($i$,$j$,$k$)の組み合わせが何通りあるか求めてください。

制約

• $1 \le N \le 10^5$
• $S$は長さ$N$の文字列である。
• $S$の各文字は英大文字である。

入力

入力は以下のように与えられる。

$N$
$S$

出力

YDKがハッピーになるような($i$,$j$,$k$)の組み合わせの個数を一行に出力せよ

小課題

1.($12$点) $N \le 300$
2.($18$点) $N \le 5000$
3.($70$点) 追加の制約はない

入出力例

入力例1

6
YDKYDK

出力例1

4

(1, 2, 3)
(1, 2, 6)
(1, 5, 6)
(4, 5, 6)
の4通りである。

入力例2

12
ABCYABCDABCK

出力例2

1

このように、'Y', 'D', 'K' 以外の文字があることもある。

入力例3

24
YDKYTAYDKYTAYDKYTAKDYYDK

出力例3

46