나누어떨어지는 분할 timer 60s memory 1024MB

10진수 숫자들로 이루어진 문자열 \mathbf{S}가 있다. \mathbf{S}의 분할(division)은 \mathbf{S}를 연속한 부분 문자열들로 나누어 만드는 것이다. 예를 들어 \mathbf{S}가 0145217이라면, 가능한 분할의 예로 014 5 21 7, 0 14 52 17이 있다. 각 숫자는 정확히 하나의 부분 문자열에만 포함되어야 하고, 각 부분 문자열은 비어 있으면 안 된다. \mathbf{S}의 길이가 L이라면, 가능한 분할의 개수는 정확히 2^{L-1}개이다.

양의 정수 \mathbf{D}가 주어졌을 때, \mathbf{S}의 분할이 \mathbf{D}로 나누어떨어진다(divisible)고 하려면 서로 이웃한 두 부분 문자열의 쌍마다, 그 둘이 10진수 정수로 나타내는 값 중 적어도 하나가 \mathbf{D}로 나누어떨어져야 한다. \mathbf{D}=7이라면, 위의 첫 번째 분할 예시는 014, 21, 7이 모두 7로 나누어떨어지므로 divisible이다. 하지만 두 번째 분할 예시는 52와 17이 서로 이웃한 부분 문자열인데 어느 쪽도 7로 나누어떨어지지 않으므로 divisible이 아니다. 또한 0145217을 그냥 0145217 하나로만 분할하면, 서로 이웃한 부분 문자열의 쌍이 존재하지 않으므로 어떤 \mathbf{D}에 대해서도 divisible이다.

\mathbf{S}와 \mathbf{D}가 주어질 때, \mathbf{D}로 divisible한 \mathbf{S}의 분할이 몇 개인지 세어라. 출력 값이 매우 커질 수 있으므로, 결과를 소수 10^9+7(1000000007)로 나눈 나머지만 출력하라.