Question
Count Substrings with Sum Divisible by K
Shreyas is given a string s of length n.
He is also given an array of 26 integers, where the value at index 0 corresponds to the character 'a', at index 1 corresponds to 'b', and so on up to index 25 for 'z'.
In other words:
-
'a'→ array[0] -
'b'→ array[1]
.....
-
'z'→ array[25]
Using this mapping, each character of the string has a numeric value.
Shreyas also has an integer k.
He wants to count the number of substrings of s such that the sum of the mapped values of all characters in that substring is divisible by k.
Your task is to print the number of such substrings.
Input
The first line contains two integers n and k — the length of the string and the divisor.
The second line contains the string s of length n.
The third line contains 26 integers — the mapping array for 'a' to 'z'.
The second line contains the string s of length n.
The third line contains 26 integers — the mapping array for 'a' to 'z'.
Output
Print a single integer — the number of substrings whose total mapped value is divisible by k.
Example
Input
4 5
abca
2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
Output
2
Explanation:
Mapping:
'a' → 2
'b' → 3
'c' → 2
Valid substrings (sum divisible by 5):
"ab" → 2+3 = 5
"bc" → 3+2 = 5
Total valid substrings = 2
4 5
abca
2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
Output
2
Explanation:
Mapping:
'a' → 2
'b' → 3
'c' → 2
Valid substrings (sum divisible by 5):
"ab" → 2+3 = 5
"bc" → 3+2 = 5
Total valid substrings = 2