Beautiful Subsequences
You are given a string. You have to find the number of beautiful subsequences in the string.
A subsequence is a sequence of characters that can be derived from a string by deleting some characters without changing the order of the remaining characters. For example, "abba" is a subsequence in "bacbdeba", but "bbaa" is not.
Beauty of a character is the sum of positions of that character in the string. For example, beauty of 'a' in the string "bacbdeba" is $2+8 = 10$, becuase the positions of 'a' in the string are $2$ and $8$. Beauty of a subsequence is the sum of beauties of the characters in the subsequence. For example, the beauty of the subsequence "aa" of string "bacbdeba" is $10+10 = 20$.
A subsequence is beautiful, if both of the following conditions hold.
- If you include a character to a subsequence, you should include all of its occurences. For example, for the string "bacbdeba", "babba" can be beautiful (if it obeys the other condition), but "ba" can not be. Because, if 'b' is chosen to be in the subsequence, all occurrences of 'b' in the string should be in the subsequence, same for 'a'.
- Beauty of the subsequence should be at least M.
You are given a string of length N. Can you find how many beautiful subsequences can be derived from the string?
Input
The first line of the input contains two integers $N$ and $M$.
The next line contains the string. The string contains lowercase English letters ('a' to 'z' ) and digits ('0' to '9' ).
$1 ≤ N ≤ 10^5 $$1 ≤ M ≤ 10^9 $
Output
Print an integer in a single line denoting the number of beautiful subsequences.
Samples
| Input | Output |
|---|---|
2 2 aa | 1 |
| Input | Output |
|---|---|
3 5 a1a | 2 |
For the first case, "aa" is the only beautiful subsequence.
For the second case, "aa" and "a1a" are the two beautiful subsequences
