Extraordinary substring is one whose sum of the mapped values of each letter is divisible by its length. Given string, count its total number of non-empty extraordinary substrings.

String	Mapped	Sum	Length	IsDivisible
a	1	1	1	Yes
s	7	7	1	Yes
d	2	2	1	Yes
f	3	3	1	Yes
as	1,7	8	2	Yes
sd	7,2	9	2	No
df	2,3	5	2	No
asd	1,7,2	10	3	No
sdf	7,2,3	12	3	Yes
asdf	1,7,2,3	13	4	No

There are 6 extraordinary substrings.

Function
countSubstrings has the following parameter(s):
string input_str: a string of length n

Returns
int: the number of non-empty extraordinary substrings

Constraints

• 1 <= n <= 2000
• All characters of input_str are lowercase English letters.

Sample Case 0
Input: bdh
Output: 4
Explanation:
The extraordinary substrings are 'b','d','h', and 'bdh'.

Sample Case 1
Input: abcd
Output: 6
Explanation:
The extraordinary substrings are 'a','b','c','d','ab', and 'cd'.