Buggy python submission (verdict: Time Limit Exceeded):
from scipy.sparse import csr_matrix


def main():
    S = {i:s for i, s in enumerate(input()[::-1])}
    MOD = 10**9 + 7
    
    DP_table = [[0] for i in range(13)]
    
    # 初期化
    digit = S[0]
    if digit == '?':
        for i in range(10):
            DP_table[i][0] = 1
    else:
        DP_table[int(digit)][0] = 1
    
    DP_table = csr_matrix(DP_table, dtype=int)
        
    transition_matrixes = {}
    for multiplier in range(13):
        for digit in range(10):
            transition_matrix = [[0 for i in range(13)] for j in range(13)]
            for k in range(13):
                transition_matrix[(digit * multiplier + k) % 13][k] = 1
            transition_matrixes[(multiplier, digit)] = csr_matrix(
                transition_matrix, dtype=int)

    for multiplier in range(13):
        transition_matrixes[multiplier] = csr_matrix(
            [[0 for i in range(13)] for j in range(13)], dtype=int)
        for digit in range(10):
            transition_matrixes[multiplier] = transition_matrixes[multiplier]\
            + transition_matrixes[(multiplier, digit)]
            
    # DP
    multiplier = 1
    for i in range(1, len(S)):
        multiplier = multiplier * 10 % 13
        digit = S[i]
        if digit == '?':
            transition_matrix = transition_matrixes[multiplier]
        else:
            transition_matrix = transition_matrixes[(multiplier, int(digit))]
        
        DP_table = transition_matrix * DP_table
        DP_table = DP_table.toarray() % MOD
        DP_table = csr_matrix(DP_table)

    print(int(DP_table[5][0].toarray()))

    
if __name__ == "__main__":
    main()


Fixed submission:
def main():
    S = {i:s for i, s in enumerate(input()[::-1])}
    MOD = 10**9 + 7

    DP_table = [[0 for i in range(13)] for j in range(len(S))]
    
    digit = S[0]
    if digit == '?':
        for i in range(10):
            DP_table[0][i] = 1
    else:
        DP_table[0][int(digit)] = 1
    
    multiplier = 1
    for i in range(1, len(S)):
        digit = S[i]
        multiplier = multiplier * 10 % 13
        if digit == '?':
            for j in range(10):
                for k in range(13):
                    DP_table[i][(j * multiplier + k) % 13] += DP_table[i-1][k]
        else:
            digit = int(digit)
            for k in range(13):
                DP_table[i][(digit * multiplier + k) % 13] += DP_table[i-1][k]
        
        for j in range(13):
            DP_table[i][j] %= MOD

    print(DP_table[len(S)-1][5])

    
if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np


def main():
    S = {i:s for i, s in enumerate(input()[::-1])}
    MOD = 10**9 + 7
    
    DP_table = np.zeros(13)
    
    # 初期化
    digit = S[0]
    if digit == '?':
        for i in range(10):
            DP_table[i] = 1
    else:
        DP_table[int(digit)] = 1
    
    # DP
    multiplier = 1
    for i in range(1, len(S)):
        digit = S[i]
        multiplier = multiplier * 10 % 13
        if digit == '?':
            transition_matrix = np.zeros((13, 13))
            for j in range(10):
                for k in range(13):
                    transition_matrix[(j * multiplier + k) % 13, k] += 1
        else:
            transition_matrix = np.zeros((13, 13))
            devided = int(digit) * multiplier
            for k in range(13):
                transition_matrix[(devided + k) % 13, k] = 1
        
        DP_table = np.dot(transition_matrix, DP_table)
        DP_table %= MOD

    print(int(DP_table[5]))

    
if __name__ == "__main__":
    main()


Fixed submission:
def main():
    S = {i:s for i, s in enumerate(input()[::-1])}
    MOD = 10**9 + 7

    DP_table = [[0 for i in range(13)] for j in range(len(S))]
    
    digit = S[0]
    if digit == '?':
        for i in range(10):
            DP_table[0][i] = 1
    else:
        DP_table[0][int(digit)] = 1
    
    multiplier = 1
    for i in range(1, len(S)):
        digit = S[i]
        multiplier = multiplier * 10 % 13
        if digit == '?':
            for j in range(10):
                for k in range(13):
                    DP_table[i][(j * multiplier + k) % 13] += DP_table[i-1][k]
        else:
            digit = int(digit)
            for k in range(13):
                DP_table[i][(digit * multiplier + k) % 13] += DP_table[i-1][k]
        
        for j in range(13):
            DP_table[i][j] %= MOD

    print(DP_table[len(S)-1][5])

    
if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    S = {i:s for i, s in enumerate(input()[::-1])}
    MOD = 10**9 + 7

    DP_table = {(i, j):0 for i in range(1, len(S)+1) for j in range(13)}
    
    digit = S[0]
    if digit == '?':
        for i in range(10):
            DP_table[(1, i)] = 1
    else:
        #DP_table[(1, int(digit))] = 1
        if digit == '0':
            DP_table[(1, 0)] = 1
        elif digit == '1':
            DP_table[(1, 1)] = 1
        elif digit == '2':
            DP_table[(1, 2)] = 1
        elif digit == '3':
            DP_table[(1, 3)] = 1
        elif digit == '4':
            DP_table[(1, 4)] = 1
        elif digit == '5':
            DP_table[(1, 5)] = 1
        elif digit == '6':
            DP_table[(1, 6)] = 1
        elif digit == '7':
            DP_table[(1, 7)] = 1
        elif digit == '8':
            DP_table[(1, 8)] = 1
        else:
            DP_table[(1, 9)] = 1
    
    multiplier = 1
    for i in range(1, len(S)):
        digit = S[i]
        multiplier = multiplier * 10 % 13
        if digit == '?':
            for j in range(10):
                for k in range(13):
                    DP_table[(i + 1, (j * multiplier + k) % 13)] += DP_table[(i, k)]
                    
        elif digit == '0':
            for k in range(13):
                DP_table[(i + 1, k % 13)] += DP_table[(i, k)]
        elif digit == '1':
            for k in range(13):
                DP_table[(i + 1, (multiplier + k) % 13)] += DP_table[(i, k)]
        elif digit == '2':
            for k in range(13):
                DP_table[(i + 1, (2 * multiplier + k) % 13)] += DP_table[(i, k)]
        elif digit == '3':
            for k in range(13):
                DP_table[(i + 1, (3 * multiplier + k) % 13)] += DP_table[(i, k)]
        elif digit == '4':
            for k in range(13):
                DP_table[(i + 1, (4 * multiplier + k) % 13)] += DP_table[(i, k)]
        elif digit == '5':
            for k in range(13):
                DP_table[(i + 1, (5 * multiplier + k) % 13)] += DP_table[(i, k)]
        elif digit == '6':
            for k in range(13):
                DP_table[(i + 1, (6 * multiplier + k) % 13)] += DP_table[(i, k)]
        elif digit == '7':
            for k in range(13):
                DP_table[(i + 1, (7 * multiplier + k) % 13)] += DP_table[(i, k)]
        elif digit == '8':
            for k in range(13):
                DP_table[(i + 1, (8 * multiplier + k) % 13)] += DP_table[(i, k)]
        else:
            for k in range(13):
                DP_table[(i + 1, (9 * multiplier + k) % 13)] += DP_table[(i, k)]
            

        
        for j in range(13):
            DP_table[(i + 1, j)] %= MOD

    print(DP_table[(len(S), 5)])

if __name__ == "__main__":
    main()

Fixed submission:
def main():
    S = {i:s for i, s in enumerate(input()[::-1])}
    MOD = 10**9 + 7

    DP_table = [[0 for i in range(13)] for j in range(len(S))]
    
    digit = S[0]
    if digit == '?':
        for i in range(10):
            DP_table[0][i] = 1
    else:
        DP_table[0][int(digit)] = 1
    
    multiplier = 1
    for i in range(1, len(S)):
        digit = S[i]
        multiplier = multiplier * 10 % 13
        if digit == '?':
            for j in range(10):
                for k in range(13):
                    DP_table[i][(j * multiplier + k) % 13] += DP_table[i-1][k]
        else:
            digit = int(digit)
            for k in range(13):
                DP_table[i][(digit * multiplier + k) % 13] += DP_table[i-1][k]
        
        for j in range(13):
            DP_table[i][j] %= MOD

    print(DP_table[len(S)-1][5])

    
if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    S = {i:s for i, s in enumerate(input()[::-1])}
    MOD = 10**9 + 7

    DP_table = {(i, j):0 for i in range(1, len(S)+1) for j in range(13)}
    
    digit = S[0]
    if digit == '?':
        for i in range(10):
            DP_table[(1, i)] = 1
    else:
        DP_table[(1, int(digit))] = 1
    
    multiplier = 1
    for i in range(1, len(S)):
        digit = S[i]
        multiplier = multiplier * 10 % 13
        if digit == '?':
            for j in range(10):
                for k in range(13):
                    DP_table[(i + 1, (j * multiplier + k) % 13)] += DP_table[(i, k)]
        else:
            for k in range(13):
                DP_table[(i + 1, (int(digit) * multiplier + k) % 13)] += DP_table[(i, k)]
        
        for j in range(13):
            DP_table[(i + 1, j)] %= MOD

    print(DP_table[(len(S), 5)])

if __name__ == "__main__":
    main()

Fixed submission:
def main():
    S = {i:s for i, s in enumerate(input()[::-1])}
    MOD = 10**9 + 7

    DP_table = [[0 for i in range(13)] for j in range(len(S))]
    
    digit = S[0]
    if digit == '?':
        for i in range(10):
            DP_table[0][i] = 1
    else:
        DP_table[0][int(digit)] = 1
    
    multiplier = 1
    for i in range(1, len(S)):
        digit = S[i]
        multiplier = multiplier * 10 % 13
        if digit == '?':
            for j in range(10):
                for k in range(13):
                    DP_table[i][(j * multiplier + k) % 13] += DP_table[i-1][k]
        else:
            digit = int(digit)
            for k in range(13):
                DP_table[i][(digit * multiplier + k) % 13] += DP_table[i-1][k]
        
        for j in range(13):
            DP_table[i][j] %= MOD

    print(DP_table[len(S)-1][5])

    
if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    S = {i:s for i, s in enumerate(input()[::-1])}
    MOD = 10**9 + 7

    DP_table = {(i, j):0 for i in range(1, len(S)+1) for j in range(13)}
    
    digit = S[0]
    if digit == '?':
        for i in range(10):
            DP_table[(1, i)] = 1
    else:
        DP_table[(1, int(digit))] = 1
    
    multiplier = 1
    for i in range(1, len(S)):
        digit = S[i]
        multiplier *= 10
        multiplier %= 13
        if digit == '?':
            for j in range(10):
                for k in range(13):
                    surplus = (j * multiplier + k) % 13
                    DP_table[(i + 1, surplus)] += DP_table[(i, k)]
        else:
            for k in range(13):
                surplus = (int(digit) * multiplier + k) % 13
                DP_table[(i + 1, surplus)] += DP_table[(i, k)]
        
        for j in range(13):        
            DP_table[(i + 1, j)] %= MOD
                
    print(DP_table[(len(S), 5)])

if __name__ == "__main__":
    main()

Fixed submission:
def main():
    S = {i:s for i, s in enumerate(input()[::-1])}
    MOD = 10**9 + 7

    DP_table = [[0 for i in range(13)] for j in range(len(S))]
    
    digit = S[0]
    if digit == '?':
        for i in range(10):
            DP_table[0][i] = 1
    else:
        DP_table[0][int(digit)] = 1
    
    multiplier = 1
    for i in range(1, len(S)):
        digit = S[i]
        multiplier = multiplier * 10 % 13
        if digit == '?':
            for j in range(10):
                for k in range(13):
                    DP_table[i][(j * multiplier + k) % 13] += DP_table[i-1][k]
        else:
            digit = int(digit)
            for k in range(13):
                DP_table[i][(digit * multiplier + k) % 13] += DP_table[i-1][k]
        
        for j in range(13):
            DP_table[i][j] %= MOD

    print(DP_table[len(S)-1][5])

    
if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    S = {i:s for i, s in enumerate(input()[::-1])}
    MOD = 10**9 + 7

    DP_table = {(i, j):0 for i in range(1, len(S)+1) for j in range(13)}
    
    digit = S[0]
    if digit == '?':
        for i in range(10):
            DP_table[(1, i)] = 1
    else:
        DP_table[(1, int(digit))] = 1
    
    multiplier = 1
    for i in range(1, len(S)):
        digit = S[i]
        multiplier *= 10
        multiplier %= 13
        if digit == '?':
            for j in range(10):
                for k in range(13):
                    surplus = (j * multiplier + k) % 13
                    DP_table[(i + 1, surplus)] += DP_table[(i, k)]
                    DP_table[(i + 1, surplus)] %= MOD
        else:
            for k in range(13):
                surplus = (int(digit) * multiplier + k) % 13
                DP_table[(i + 1, surplus)] += DP_table[(i, k)]
                DP_table[(i + 1, surplus)] %= MOD
                
    print(DP_table[(len(S), 5)])

if __name__ == "__main__":
    main()

Fixed submission:
def main():
    S = {i:s for i, s in enumerate(input()[::-1])}
    MOD = 10**9 + 7

    DP_table = [[0 for i in range(13)] for j in range(len(S))]
    
    digit = S[0]
    if digit == '?':
        for i in range(10):
            DP_table[0][i] = 1
    else:
        DP_table[0][int(digit)] = 1
    
    multiplier = 1
    for i in range(1, len(S)):
        digit = S[i]
        multiplier = multiplier * 10 % 13
        if digit == '?':
            for j in range(10):
                for k in range(13):
                    DP_table[i][(j * multiplier + k) % 13] += DP_table[i-1][k]
        else:
            digit = int(digit)
            for k in range(13):
                DP_table[i][(digit * multiplier + k) % 13] += DP_table[i-1][k]
        
        for j in range(13):
            DP_table[i][j] %= MOD

    print(DP_table[len(S)-1][5])

    
if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    S = {i:s for i, s in enumerate(input()[::-1])}
    MOD = 10**9 + 7

    DP_table = {(i, j):0 for i in range(1, len(S)+1) for j in range(13)}
    
    digit = S[0]
    if digit == '?':
        for i in range(10):
            DP_table[(1, i)] = 1
    else:
        DP_table[(1, int(digit))] = 1
    
    multiplier = 1
    for i in range(1, len(S)):
        digit = S[i]
        multiplier *= 10
        multiplier %= 13
        if digit == '?':
            for j in range(10):
                devided = j * multiplier
                for k in range(13):
                    surplus = (devided + k) % 13
                    DP_table[(i + 1, surplus)] += DP_table[(i, k)] % MOD
                    DP_table[(i + 1, surplus)] %= MOD
        else:
            for k in range(13):
                surplus = (int(digit) * multiplier + k) % 13
                DP_table[(i + 1, surplus)] += DP_table[(i, k)] % MOD
                DP_table[(i + 1, surplus)] %= MOD
                
    print(DP_table[(len(S), 5)])

if __name__ == "__main__":
    main()

Fixed submission:
def main():
    S = {i:s for i, s in enumerate(input()[::-1])}
    MOD = 10**9 + 7

    DP_table = [[0 for i in range(13)] for j in range(len(S))]
    
    digit = S[0]
    if digit == '?':
        for i in range(10):
            DP_table[0][i] = 1
    else:
        DP_table[0][int(digit)] = 1
    
    multiplier = 1
    for i in range(1, len(S)):
        digit = S[i]
        multiplier = multiplier * 10 % 13
        if digit == '?':
            for j in range(10):
                for k in range(13):
                    DP_table[i][(j * multiplier + k) % 13] += DP_table[i-1][k]
        else:
            digit = int(digit)
            for k in range(13):
                DP_table[i][(digit * multiplier + k) % 13] += DP_table[i-1][k]
        
        for j in range(13):
            DP_table[i][j] %= MOD

    print(DP_table[len(S)-1][5])

    
if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    S = {i:s for i, s in enumerate(input()[::-1])}
    MOD = 10**9 + 7

    DP_table = {(i, j):0 for i in range(1, len(S)+1) for j in range(13)}
    
    digit = S[0]
    if digit == '?':
        for i in range(10):
            DP_table[(1, i)] = 1
    else:
        DP_table[(1, int(digit))] = 1
    
    multiplier = 1
    for i in range(1, len(S)):
        digit = S[i]
        multiplier *= 10
        multiplier %= 13
        if digit == '?':
            for j in range(10):
                devided = j * multiplier
                for k in range(13):
                    surplus = (devided + k) % 13
                    DP_table[(i + 1, surplus)] += DP_table[(i, k)] % MOD
                    DP_table[(i + 1, surplus)] %= MOD
        else:
            for k in range(13):
                surplus = (int(digit) * multiplier + k) % 13
                DP_table[(i + 1, surplus)] += DP_table[(i, k)] % MOD
                DP_table[(i + 1, surplus)] %= MOD
                
    print(DP_table[(len(S), 5)])

if __name__ == "__main__":
    main()

Fixed submission:
def main():
    S = {i:s for i, s in enumerate(input()[::-1])}
    MOD = 10**9 + 7

    DP_table = [[0 for i in range(13)] for j in range(len(S))]
    
    digit = S[0]
    if digit == '?':
        for i in range(10):
            DP_table[0][i] = 1
    else:
        DP_table[0][int(digit)] = 1
    
    multiplier = 1
    for i in range(1, len(S)):
        digit = S[i]
        multiplier = multiplier * 10 % 13
        if digit == '?':
            for j in range(10):
                for k in range(13):
                    DP_table[i][(j * multiplier + k) % 13] += DP_table[i-1][k]
        else:
            digit = int(digit)
            for k in range(13):
                DP_table[i][(digit * multiplier + k) % 13] += DP_table[i-1][k]
        
        for j in range(13):
            DP_table[i][j] %= MOD

    print(DP_table[len(S)-1][5])

    
if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict


def main():
    S = {i:s for i, s in enumerate(input()[::-1])}
    MOD = 10**9 + 7

    DP_table = defaultdict(int)
    
    digit = S[0]
    if digit == '?':
        for i in range(10):
            DP_table[(1, i)] = 1
    else:
        DP_table[(1, int(digit))] = 1
    
    power_ten = 1
    for i in range(1, len(S)):
        digit = S[i]
        power_ten *= 10
        if digit == '?':
            for j in range(10):
                devided = j * power_ten
                for k in range(13):
                    surplus = (devided + k) % 13
                    DP_table[(i + 1, surplus)] += DP_table[(i, k)] % MOD
                    DP_table[(i + 1, surplus)] %= MOD
        else:
            for k in range(13):
                surplus = (int(digit) * power_ten + k) % 13
                DP_table[(i + 1, surplus)] += DP_table[(i, k)] % MOD
                DP_table[(i + 1, surplus)] %= MOD
                
    print(DP_table[(len(S), 5)])

if __name__ == "__main__":
    main()

Fixed submission:
def main():
    S = {i:s for i, s in enumerate(input()[::-1])}
    MOD = 10**9 + 7

    DP_table = [[0 for i in range(13)] for j in range(len(S))]
    
    digit = S[0]
    if digit == '?':
        for i in range(10):
            DP_table[0][i] = 1
    else:
        DP_table[0][int(digit)] = 1
    
    multiplier = 1
    for i in range(1, len(S)):
        digit = S[i]
        multiplier = multiplier * 10 % 13
        if digit == '?':
            for j in range(10):
                for k in range(13):
                    DP_table[i][(j * multiplier + k) % 13] += DP_table[i-1][k]
        else:
            digit = int(digit)
            for k in range(13):
                DP_table[i][(digit * multiplier + k) % 13] += DP_table[i-1][k]
        
        for j in range(13):
            DP_table[i][j] %= MOD

    print(DP_table[len(S)-1][5])

    
if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict


def main():
    S = input()
    S = S[::-1]
    MOD = 10**9 + 7

    DP_table = defaultdict(int)
    
    digit = S[0]
    if digit == '?':
        for i in range(10):
            DP_table[(1, i)] = 1
    else:
        DP_table[(1, int(digit))] = 1
    
    power_ten = 1
    for i in range(1, len(S)):
        digit = S[i]
        power_ten *= 10
        if digit == '?':
            for j in range(10):
                devided = j * power_ten
                for k in range(13):
                    surplus = (devided + k) % 13
                    DP_table[(i + 1, surplus)] += DP_table[(i, k)] % MOD
                    DP_table[(i + 1, surplus)] %= MOD
        else:
            for k in range(13):
                surplus = (int(digit) * power_ten + k) % 13
                DP_table[(i + 1, surplus)] += DP_table[(i, k)] % MOD
                DP_table[(i + 1, surplus)] %= MOD
                
    print(DP_table[(len(S), 5)])

if __name__ == "__main__":
    main()

Fixed submission:
def main():
    S = {i:s for i, s in enumerate(input()[::-1])}
    MOD = 10**9 + 7

    DP_table = [[0 for i in range(13)] for j in range(len(S))]
    
    digit = S[0]
    if digit == '?':
        for i in range(10):
            DP_table[0][i] = 1
    else:
        DP_table[0][int(digit)] = 1
    
    multiplier = 1
    for i in range(1, len(S)):
        digit = S[i]
        multiplier = multiplier * 10 % 13
        if digit == '?':
            for j in range(10):
                for k in range(13):
                    DP_table[i][(j * multiplier + k) % 13] += DP_table[i-1][k]
        else:
            digit = int(digit)
            for k in range(13):
                DP_table[i][(digit * multiplier + k) % 13] += DP_table[i-1][k]
        
        for j in range(13):
            DP_table[i][j] %= MOD

    print(DP_table[len(S)-1][5])

    
if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import bisect
import heapq
import math
import queue
import sys
from collections import defaultdict


def main():
    S = input()
    S = S[::-1]
    MOD = 10**9 + 7

    DP_table = defaultdict(int)
    
    digit = S[0]
    if digit == '?':
        for i in range(10):
            DP_table[(1, i)] = 1
    else:
        DP_table[(1, int(digit))] = 1
    
    power_ten = 1
    for i in range(1, len(S)):
        digit = S[i]
        power_ten *= 10
        if digit == '?':
            for j in range(10):
                devided = j * power_ten
                for k in range(13):
                    surplus = (devided + k) % 13
                    DP_table[(i + 1, surplus)] += DP_table[(i, k)] % MOD
                    DP_table[(i + 1, surplus)] %= MOD
        else:
            for k in range(13):
                surplus = (int(digit) * power_ten + k) % 13
                DP_table[(i + 1, surplus)] += DP_table[(i, k)] % MOD
                DP_table[(i + 1, surplus)] %= MOD
                
    print(DP_table[(len(S), 5)])

if __name__ == "__main__":
    main()

Fixed submission:
def main():
    S = {i:s for i, s in enumerate(input()[::-1])}
    MOD = 10**9 + 7

    DP_table = [[0 for i in range(13)] for j in range(len(S))]
    
    digit = S[0]
    if digit == '?':
        for i in range(10):
            DP_table[0][i] = 1
    else:
        DP_table[0][int(digit)] = 1
    
    multiplier = 1
    for i in range(1, len(S)):
        digit = S[i]
        multiplier = multiplier * 10 % 13
        if digit == '?':
            for j in range(10):
                for k in range(13):
                    DP_table[i][(j * multiplier + k) % 13] += DP_table[i-1][k]
        else:
            digit = int(digit)
            for k in range(13):
                DP_table[i][(digit * multiplier + k) % 13] += DP_table[i-1][k]
        
        for j in range(13):
            DP_table[i][j] %= MOD

    print(DP_table[len(S)-1][5])

    
if __name__ == "__main__":
    main()