Winnie has run out of backstory to give you, so she just gave you a question instead.
Given a string consisting of only integers, find the number of substrings of that are divisible by .
Input Specification
The first line will contain a string . will only contain digits, and will not contain leading s.
Output Specification
Output the number of substrings of that are divisible by .
Subtasks
Subtask 1 [10%]
Subtask 2 [20%]
Subtask 3 [70%]
No further constraints
Sample Input 1
9216
Sample Output 1
1
Sample Input 2
4608046080
Sample Output 1
8
Comments