Floyd算法（Python）

思路：Floyd算法。把输入的a, b边建邻接矩阵，然后跑一遍Floyd算法，之后再算出每个数位有几种变化情况。最终，遍历输入x的每一个数位，把每个数位可能的变化情况进行累乘并取mod即可。为什么？因为每一个数位独立，那就可以用乘法原理把各自的可能性给乘起来，就可以得到最终答案了

代码：

import sys
input = lambda: sys.stdin.readline().strip()

import math
inf = 10 ** 18

def I():
    return input()

def II():
    return int(input())

def MII():
    return map(int, input().split())

def LI():
    return input().split()

def LII():
    return list(map(int, input().split()))

def LFI():
    return list(map(float, input().split()))

fmax = lambda x, y: x if x > y else y
fmin = lambda x, y: x if x < y else y
isqrt = lambda x: int(math.sqrt(x))

'''

'''

def solve():
    mod = 10 ** 4 + 7
    x, n = MII()

    g = [[False] * 10 for _ in range(10)]
    for i in range(10):
        g[i][i] = True

    for _ in range(n):
        a, b = MII()
        g[a][b] = True

    for k in range(10):
        for i in range(10):
            for j in range(10):
                if g[i][k] and g[k][j]:
                    g[i][j] = True

    cnt = [0] * 10
    for i in range(10):
        for j in range(10):
            if g[i][j]:
                cnt[i] += 1

    ans = 1
    for c in str(x):
        ans = ans * cnt[int(c)] % mod

    print(ans)

t = 1
for _ in range(t):
    solve()