ABC135 D

D問題

桁DPを使用する
1の位,10の位,100の位...と桁毎にパターンを数えあげていく
10の位のパターン = 1の位のパターン + 10の位のパターン
100の位のパターン = 10の位のパターン + 100の位のパターン

python3だとTLEになっちゃうのでpypyで提出
pypyでもこまめに値を小さくしないとTLEになる

ss = input()
# 13で割ったあまり0~12のパターンを格納する
dp = [0] * 13
# 0 % 13 = 0なのであまり0の初期値1
dp[0] = 1
# 出力条件
mod = 10 ** 9 + 7
# 対象の位
mul = 1

# 文字列の後ろから順に数える
for s in ss[::-1]:
    # 次のdpを用意
    next_dp = [0] * 13

    if s == '?':
        # 文字列'0'~'9'
        for num in range(10):
            # あまり0~12
            for i in range(13):
                # パターン数を更新
                next_dp[(num * mul + i) % 13] += dp[i]
                # 値を小さくする
                next_dp[(num * mul + i) % 13] %= mod
    else:
        num = int(s)
        # ?の場合と同様
        for i in range(13):
            next_dp[(num * mul + i) % 13] += dp[i]
            next_dp[(num * mul + i) % 13] %= mod

    # 1の位->10の位->100の位...
    mul *= 10
    # 値を小さくする
    mul %= 13

    dp = next_dp

# あまりが5となるパターン数
print(dp[5])