Submission #5119387

---

Source Code Expand

D = int(input())
N = int(input())+1
liN = list(map(int, list(str(N))))
P = 10**9+7
s = 0
k = len(str(N))
ans = -1
for a in range(k):
    X = [0] * D
    for i in range(liN[a]):
        X[(s+i)%D] += 1
    for i in range(a, k - 1):
        Y = [0] * D
        for j in range(D):
            for l in range(10):
                Y[(j+l)%D] = (Y[(j+l)%D]+X[j])%P
        X = Y
    ans = (ans + X[0]) % P
    s = (s+liN[a]) % D
print(ans)

Submission Info

Judge Result