P4349 [CERC2015] Digit Division

We are given a sequence of n decimal digits. The sequence needs to be partitioned into one or more contiguous subsequences such that each subsequence, when interpreted as a decimal number, is divisible by a given integer m. Find the number of different such partitions modulo $10^9 +7$. When determining if two partitions are different, we only consider the locations of subsequence boundaries rather than the digits themselves, e.g. partitions $2|22$ and $22|2$ are considered different.

无

无

Central Europe Regional Contest 2015 Problem D