D - Tea Set
Darjeeling
2
s
1024
MB
250
点
問題文
Kaffa くんはティーブレイクを楽しむために紅茶を選んでいます．
今，Kaffa くんの机の上には $N$ 個の紅茶が一列に並んでいます．
また，それぞれの紅茶には種類があり，長さ $N$ の英小文字からなる文字列 $S$ で表されます．$i$ 番目の紅茶の種類は $S$ の $i$ 番目の文字 $S_i$ で表されます．
Kaffa くんはこのなかから連続するいくつかの紅茶を選択するつもりです．また，Kaffa 君は味をたくさん楽しむために，選んだ紅茶の中にちょうど $K$ 種類の紅茶が含まれるように選ぼうと考えています．
そのような選び方の個数を求めて下さい．
制約
- $1 \leq N \leq 2000$
- $1 \leq K \leq 26$
- $N, K$ は整数
- $S$ は英小文字からなる $N$ 文字の文字列
入力
入力は標準入力から以下の形式で与えられる．
$N$ $K$
$S$
出力
選び方の個数を整数で一行に出力してください．
入力例 1
7 2
kiritan
出力例 1
7
Kaffa くんは二種類の紅茶を飲みたいです．
例えば，左から 2, 3, 4 番目の紅茶を選べば，この中に含まれる紅茶の種類は i が 2 つと r が 1 つで種類数は 2 なため Kaffa くんはティーブレイクを楽しめます．
ところが，左から 1, 2, 3 番目の紅茶を選ぶと，この中に含まれる紅茶の種類は k, i, r がそれぞれ 1 つずつで種類数は 3 なため Kaffa くんはティーブレイクを楽しむことが出来ません．
1 番目と 3 番目のような選び方は出来ないことに注意して下さい．
入力例 2
8 1
ddccddcc
出力例 2
12