Counting Friendly Substrings

Given a digit string \(S\) of length \(L\) consisting of digits 0 to 9, there are a total of \(\frac{L(L+1)}{2}\) contiguous substrings. A substring is called a friendly substring with respect to a positive integer \(p\) if the number represented by this substring (leading zeros are allowed) is divisible by \(p\).

For example, if \(S = "12342"\) and \(p = 2\), the contiguous substrings of \(S\) are:

• "1"
• "12"
• "123"
• "1234"
• "12342"
• "2"
• "23"
• "234"
• "2342"
• "3"
• "34"
• "342"
• "4"
• "42"
• "2"

Among these, the substrings whose numerical values are divisible by \(2\) are "12", "1234", "12342", "2", "234", "2342", "34", "342", "4", "42", and the second occurrence of "2" (each occurrence is counted separately). Thus, there are 11 friendly substrings.

Your task is to compute the number of friendly substrings of \(S\) for a given positive integer \(p\).

inputFormat

The input consists of two lines:

1. The first line contains the digit string \(S\).
2. The second line contains the positive integer \(p\).

outputFormat

Output a single integer representing the number of friendly substrings that are divisible by \(p\).

sample

12342
2

11