Roy was given a string s containing only uppercase English letters. He can do any number of modifications on s. The allowed modifications are:
1)He can add underscore ('_') character in anywhere inside the string.
2)He can delete any existing character of the string.
3)He can swap any two characters of the string.Every character in the resulting string has a value equal to its ASCII value.
After doing the modifications the string needs to have the following properties:
The length of the string should be equal to n.There should be at least k characters of higher value between two equal letters (Note that, underscore is not a letter).Calculate how many different strings Roy can achieve modulo 1000003 (10^6+3).
Note: In the increasing order of ASCII value, we can arrange the alphabet in the following way:
A
You must be logged in to submit a solution.
1)He can add underscore ('_') character in anywhere inside the string.
2)He can delete any existing character of the string.
3)He can swap any two characters of the string.Every character in the resulting string has a value equal to its ASCII value.
After doing the modifications the string needs to have the following properties:
The length of the string should be equal to n.There should be at least k characters of higher value between two equal letters (Note that, underscore is not a letter).Calculate how many different strings Roy can achieve modulo 1000003 (10^6+3).
Note: In the increasing order of ASCII value, we can arrange the alphabet in the following way:
A
Input Format
The first line contains two space separated integers n (1≤n≤109) and k (0≤k≤109). The second line contains string s containing only uppercase English letters (1≤|s|≤2500).
Sample Input
3 1
LBB
Output Format Print the number of different strings Roy can achieve modulo 1000003 (10^6+3).
Sample Output
15You must be logged in to submit a solution.