408922: GYM103380 H Label Cropping

The elves are creating an ID label for a toy part but their supervisor has a very weird, specific rule. The supervisor has a favorite number, and the ID label the elves must create must be divisible by this special number. The supervisor also hates the numbers 2 and 5, and his favorite number will not be divisible by either.

However, the label printer was recently used by a nefarious being to try to sabotage Christmas, and is freshly out of ink! The only thing the elves have is a printed label of a GINORMOUS integer. The label printer also does not have a 0 digit.

The elves realize that there might be ways to cut the label such that they can create a label with an ID divisible by the supervisor's favorite number, and would like to know how many ways they can do so. The resulting label must be a contiguous portion of the original, and the elves only need one label.

In other words, find the number of ways to remove some (possibly zero) digits from the front and back such that the resulting (nonempty) label is divisible by the supervisor's favorite number.

First line with $$$N$$$, the ginormous integer printed by the nefarious being $$$1 \leq N \leq 10^{10^6}$$$. No digit in $$$N$$$ is 0.

Second line with K, the supervisor's favorite integer $$$1 \leq K \leq 5000$$$, where $$$K$$$ is not divisible by 2 or 5.

One integer denoting the number of ways to cut the label.

72476
3

3

19987589742315
19

6

61413
4553

0