思路

1. 枚举 $3$ 的个数以及 $7$ 的个数，假设 $3$ 的个数为 $i$，$7$ 的个数为 $j$，那么非 $3, 7$ 的个数即为 $n - i - j$。
2. 在长度为 $n$ 的字符串中选取 $i$ 的方案数为 $C^i_n$，在剩余 $n - i$ 个位置选取 $j$ 个的方案数为 $C^j_{n - i}$，剩余位置个数为 $n - i - j$，可选择的内容为 $\{1, 2, 4, 5, 6, 8, 9\}$，共七个，故方案数为 $7^{n - i - j}$，乘积即为答案。

MOD = int(1e9 + 7)

def qmi(a, b):
    res = 1
    while b > 0:
        if b & 1:
            res = res * a % MOD
        a = a * a % MOD
        b >>= 1
    return res

n = 10000
N = int(1e4 + 10)
f = [[0 for i in range(N)] for i in range(N)]
def init():
    for i in range(0, n + 1):
        for j in range(0, i + 1):
            if j == 0:
                f[i][j] = 1
            else:
                f[i][j] = (f[i - 1][j] + f[i - 1][j - 1]) % MOD

init()

res = 0
for i in range(1, n - 1 + 1):
    for j in range(1, n - i + 1):
        res = (res + f[n][i] * f[n - i][j] * qmi(7, n - i - j)) % MOD

print(res)

运行结果：

157509472