Submission #32514921

---

Source Code Expand

mod = 1_000_000_007

def mat_mul(a, b):
    m = [[0]*len(a) for _ in range(len(b[0]))]
    *b, = zip(*b)
    
    for i, r in enumerate(m):
        for j in range(len(r)):
            r[j] = sum([x * y % mod for x, y in zip(a[i], b[j])])
            r[j] %= mod
            
    return m
            
    
def mat_pow(a, n):
    ret = [[0]*len(a) for _ in range(len(a))]
    for i in range(len(a)):
        ret[i][i] = 1
    
    while n:
        if n & 1:
            ret = mat_mul(ret, a)
        a = mat_mul(a, a)
        n >>= 1

    return ret


def kaisetsu2(N, B, K, c):
    A = [[0]*B for _ in range(B)]
    
    for i in range(B):
        for j in c:
            nex = (i*10 + j) % B
            A[i][nex] += 1
    
    return mat_pow(A, N)[0][0]
  

N, B, K, *c = map(int, open(0).read().split())
print(kaisetsu2(N, B, K, c))

Submission Info

Judge Result