Matching Pairs

Let X and Y be two unempty strings over unempty alphabet A and let K be a non-negative integer.
We say that (X, Y) is a K-pair if Y can be obtained from X by changing some characters in X on exactly K different positions.
We say that (X, Y) is a K-reduced pair if Y can be obtained from X by removing a substring of length K from X.

Let S be a string. Let S1 and S2 be two unempty substrings of S. Let L be a positive integer, let K be a non-negative integer, both not bigger than the length of S.
We say that S1 and S2 are a (L,K)-matching pair if all following conditions hold.

  1. The length of S1 is L, the length of S2 is L or L− K.
  2. Substrings S1 and S2 do not overlap, that is, no position in S is simultaneously part of S1 and S2.
  3. The pair (S1, S2) is a K-pair or a K-reduced pair.
We say that two (L, K)-matching pairs (S1, S2) and (T1, T2) are different if one of them is a K-pair and the other is a K-reduced pair.
When two (L, K)-matching pairs (S1, S2) and (T1, T2) are both a K-pair, we say that (S1, S2) and (T1, T2) are different if the set of all positions in S occupied by (S1, S2) differs from the set of all positions in S occupied by (T1, T2).
When two (L, K)-matching pairs (S1, S2) and (T1, T2) are both a K-reduced pair, we say that (S1, S2) and (T1, T2) are different if the set of all positions in S occupied by S1 differs from the set of all positions in S occupied by T1 or the set of all positions in S occupied by S2 differs from the set of all positions in S occupied by T2.

Note that two different (L, K)-matching pairs might sometimes contain identical sequences of charaters. This fact is illustrated in Example 2 below.

The task

You are given the alphabet A, the string S over A and two integers L and K. Find the number of different (L, K)-matching pairs in S.

Input

The input contains two text lines. The first line contains three integers A, L, K. The second line contains a string S over the the alphabet consisting of first A lowercase letters of English alphabet. There are no blanks or spaces on the second line.
It holds, 1 ≤ A ≤ 26, 0 ≤ K < L ≤ 500, L < |S| ≤ 2 000 .

Output

The output contains one text line with one integer representing the number of (L, K)-matching pairs in S.

Example 1

Input
8 5 3
hhgccchggbcbfbaddeca
Output
9
Comment
The (5, 3)-matching pairs in the input string are given below, the positions of the respective substrings in the input string are included. 
(hhgcc)  (chggb)  [ 0 --  4]  [ 5 --  9]
(hgccc)  (ggbcb)  [ 1 --  5]  [ 7 -- 11]
(gccch)  (ggbcb)  [ 2 --  6]  [ 7 -- 11]
(gccch)  (gbcbf)  [ 2 --  6]  [ 8 -- 12]
(hgccc)  (hg)     [ 1 --  5]  [ 6 --  7]
(ccchg)  (hg)     [ 3 --  7]  [ 1 --  2]
(chggb)  (cb)     [ 5 --  9]  [10 -- 11]
(hggbc)  (hg)     [ 6 -- 10]  [ 1 --  2]
(cbfba)  (ca)     [10 -- 14]  [18 -- 19]

Example 2

Input
7 3 0
cabdcabecabfcabgcab
Output
10
Comment
All 10 (3,0)- matching pairs contain the same sequence 'cab' in their respective substrings.

Example 3

Input
3 7 2
abbaccbbbacbccaccacbbccbbbcabbcccababcbb
Output
24
Comment
The (7, 2)-matching pairs in the input string are given below, the positions of the respective substrings in the input string are included. 
(abbaccb, acbbccb)    [ 0 --  6]  [17 -- 23]
(abbaccb, abbccca)    [ 0 --  6]  [27 -- 33]
(bbaccbb, cbbccbb)    [ 1 --  7]  [18 -- 24]
(bbaccbb, bbccbbb)    [ 1 --  7]  [19 -- 25]
(bbaccbb, bbbcabb)    [ 1 --  7]  [23 -- 29]
(bbaccbb, bbcccab)    [ 1 --  7]  [28 -- 34]
(bbaccbb, ababcbb)    [ 1 --  7]  [33 -- 39]
(accbbba, bccbbbc)    [ 3 --  9]  [20 -- 26]
(ccbbbac, ccbbbca)    [ 4 -- 10]  [21 -- 27]
(cbbbacb, cbbbcab)    [ 5 -- 11]  [22 -- 28]
(bbbacbc, bbcabbc)    [ 6 -- 12]  [24 -- 30]
(bbacbcc, bcabbcc)    [ 7 -- 13]  [25 -- 31]
(ccacbbc, ccababc)    [15 -- 21]  [31 -- 37]
(cacbbcc, cabbccc)    [16 -- 22]  [26 -- 32]
(bbccbbb, bbcccab)    [19 -- 25]  [28 -- 34]
(bbaccbb, bccbb)      [ 1 --  7]  [20 -- 24]
(baccbbb, ccbbb)      [ 2 --  8]  [21 -- 25]
(ccbbbac, ccbbb)      [ 4 -- 10]  [21 -- 25]
(bbacbcc, bbacc)      [ 7 -- 13]  [ 1 --  5]
(bccacca, bccca)      [11 -- 17]  [29 -- 33]
(accacbb, accbb)      [14 -- 20]  [ 3 --  7]
(bbccbbb, ccbbb)      [19 -- 25]  [ 4 --  8]
(ccbbbca, ccbbb)      [21 -- 27]  [ 4 --  8]
(bbcccab, bbccb)      [28 -- 34]  [19 -- 23]

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set