Each character of the English alphabet has been mapped to a digit as shown below.
A string is divisible if the sum of the mapped values of its characters is divisible by its length.
Given a string s, return the number of divisible substrings of s.
A substring is a contiguous non-empty sequence of characters within a string.
Example 1:
Input: word = "asdf"
Output: 6
Explanation:The table above contains the details about every substring of word, and we can see that 6 of them are divisible.
Example 2:
Input: word = "bdh"
Output: 4
Explanation:The 4 divisible substrings are: "b", "d", "h", "bdh".
It can be shown that there are no other substrings of word that are divisible.
Example 3:
Input: word = "abcd"
Output: 6
Explanation:The 6 divisible substrings are: "a", "b", "c", "d", "ab", "cd".
It can be shown that there are no other substrings of word that are divisible.
1 <= word.length <= 2000wordconsists only of lowercase English letters.
input:
output: