Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
def d_maze_master(INF=float('inf')):
    from collections import deque
    H, W = [int(i) for i in input().split()]
    Maze = [list(input()) for _ in range(H)]

    start_row, start_col = None, None
    for row in range(H):
        for col in range(W):
            if Maze[row][col] == '.':
                start_row, start_col = row, col
                break
        else:
            continue
        break

    diff = ((-1, 0), (0, 1), (1, 0), (0, -1))

    def is_inside(row, col):
        return 0 <= row < H and 0 <= col < W

    queue = deque([(start_row, start_col)])
    dist = [[INF for _ in range(W)] for _ in range(H)]
    dist[start_row][start_col] = 0
    while queue:
        row, col = queue.pop()
        for dr, dc in diff:
            nr, nc = row + dr, col + dc
            if is_inside(nr, nc) and Maze[nr][nc] != '#' and dist[nr][nc] == INF:
                queue.appendleft((nr, nc))
                dist[nr][nc] = dist[row][col] + 1

    start_row, start_col = None, None
    maximum = 0
    for row in range(H):
        for col in range(W):
            if Maze[row][col] != '#' and dist[row][col] > maximum:
                maximum = dist[row][col]
                start_row, start_col = row, col

    queue = deque([(start_row, start_col)])
    dist = [[INF for _ in range(W)] for _ in range(H)]
    dist[start_row][start_col] = 0
    while queue:
        row, col = queue.pop()
        for dr, dc in diff:
            nr, nc = row + dr, col + dc
            if is_inside(nr, nc) and Maze[nr][nc] != '#' and dist[nr][nc] == INF:
                queue.appendleft((nr, nc))
                dist[nr][nc] = dist[row][col] + 1

    ans = 0
    for row in range(H):
        for col in range(W):
            if Maze[row][col] != '#' and dist[row][col] > ans:
                ans = dist[row][col]
    return ans

print(c_welcome_to_atcoder())

Fixed submission:
def d_maze_master(INF=float('inf')):
    from collections import deque
    H, W = [int(i) for i in input().split()]
    Maze = [list(input()) for _ in range(H)]

    def bfs(start_row, start_col):
        diff = ((-1, 0), (0, 1), (1, 0), (0, -1))

        def is_inside(row, col):
            return 0 <= row < H and 0 <= col < W

        queue = deque([(start_row, start_col)])
        dist = [[INF for _ in range(W)] for _ in range(H)]
        dist[start_row][start_col] = 0
        while queue:
            row, col = queue.pop()
            for dr, dc in diff:
                nr, nc = row + dr, col + dc
                if is_inside(nr, nc) and Maze[nr][nc] != '#' and dist[nr][nc] == INF:
                    queue.appendleft((nr, nc))
                    dist[nr][nc] = dist[row][col] + 1
        return dist

    ans = 0
    for start_row in range(H):
        for start_col in range(W):
            if Maze[start_row][start_col] == '#':
                continue
            dist = bfs(start_row, start_col)
            for row in range(H):
                for col in range(W):
                    if Maze[row][col] != '#':
                        ans = max(ans, dist[row][col])
    return ans

print(d_maze_master())
Buggy python submission (verdict: Runtime Error):
def d_semi_common_multiple():
    from math import gcd
    from functools import reduce
    N, M = [int(i) for i in input().split()]
    A = [int(i) // 2 for i in input().split()]  # 先に2で割っておく

    def count_divide_2(n):
        """n に含まれる因数 2 の指数"""
        return (n & -n).bit_length()

    def lcm(a, b):
        return a * b // gcd(a, b)

    # A の全要素について，2で割れる回数は等しいか？
    tmp = count_divide_2(A[0])
    for a in A:
        if count_divide_2(a) != tmp:
            return 0

    t = reduce(lambda x, y: lcm(x, y), A)
    return (M // t) - (M // (2 * t))

print(d_semi_common_multiple())

Fixed submission:
def d_semi_common_multiple():
    from fractions import gcd
    from functools import reduce
    N, M = [int(i) for i in input().split()]
    A = [int(i) // 2 for i in input().split()]  # 先に2で割っておく

    def count_divide_2(n):
        ret = 0
        while n % 2 == 0:
            ret += 1
            n //= 2
        return ret

    def lcm(a, b):
        return a * b // gcd(a, b)

    # A の全要素について、2で割れる回数は等しいか？
    tmp = count_divide_2(A[0])
    for a in A:
        if count_divide_2(a) != tmp:
            return 0

    t = reduce(lambda x, y: lcm(x, y), A)
    return M // t - M // (2 * t)

print(d_semi_common_multiple())
Buggy python submission (verdict: Runtime Error):
def f_playing_tag_on_tree():
    N, U, V = [int(i) for i in input().split()]
    Edges = [[int(i) for i in input().split()] for j in range(N - 1)]

    tree = [[] for _ in range(N)]
    for u, v in Edges:
        tree[u - 1].append(v - 1)
        tree[v - 1].append(u - 1)

    depth = [-1] * N

    def dfs(current, parent, dep):
        depth[current] = dep

        for child in tree[current]:
            if child == parent:
                continue
            dfs(child, current, dep + 1)
        return None
    dfs(V - 1, -1, 0)
    return max(depth) - 1

print(f_playing_tag_on_tree())

Fixed submission:
def f_playing_tag_on_tree():
    from collections import deque

    def bfs(tree, distance, first_pos):
        q = deque([(first_pos, -1)])
        while q:
            current, parent = q.pop()
            for child in tree[current]:
                if child == parent:
                    continue
                distance[child] = distance[current] + 1
                q.appendleft((child, current))

    N, U, V = map(int, input().split())
    tree = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        tree[a - 1].append(b - 1)
        tree[b - 1].append(a - 1)

    # 両者について、最初にいる場所から他の頂点への移動回数を求める
    dist_aoki = [0] * N
    bfs(tree, dist_aoki, V - 1)
    dist_takahashi = [0] * N
    bfs(tree, dist_takahashi, U - 1)

    ans = 0
    for aoki, takahashi in zip(dist_aoki, dist_takahashi):
        # 注目した頂点 v には高橋くんの方が先に到達できる
        if aoki > takahashi:
            # 青木くんは v の親で高橋くんを捕まえることになるので、
            # v までの距離 - 1 が解となりうる
            ans = max(ans, aoki - 1)
    return ans

print(f_playing_tag_on_tree())
Buggy python submission (verdict: Time Limit Exceeded):
def d_lucky_pin():
    N = int(input())
    S = input()

    # 暗証番号を全探索
    ans = 0
    for v in range(1000):
        pin = '{0:03}'.format(v)
        current_searching = 0

        for ch in S:
            if ch == pin[current_searching]:
                current_searching += 1
            if current_searching == 3:
                ans += 1
                break
    return ans

print(d_lucky_pin())

Fixed submission:
def d_lucky_pin():
    N = int(input())
    S = input()

    # 暗証番号を全探索
    ans = 0
    for v in range(1000):
        pin = '{0:03}'.format(v)
        current_searching = 0

        for ch in S:
            if ch == pin[current_searching]:
                current_searching += 1
            if current_searching == 3:
                ans += 1
                break
    return ans

print(d_lucky_pin())
Buggy python submission (verdict: Time Limit Exceeded):
def e_all_you_can_eat():
    N, T = [int(i) for i in input().split()]
    Dishes = sorted([[int(i) for i in input().split()] for j in range(N)])

    # dp[i][j]: i 番目までの料理を j 分以内に完食できるように選んだとき、満足度の和の最大値
    dp = [[0] * (T + 1) for _ in range(N + 1)]
    ans = 0
    dp[0][0] = 0  # 食べていないときの満足度は 0 とする
    for i in range(1, N + 1):
        for j in range(T):
            dp[i][j] = dp[i - 1][j]  # i 番目を食べなかった場合

            # i 番目を食べることにした場合
            # (最後の料理は、ラストオーダー時刻が来ていなければ
            # 頼んで食いっぱなしにしてよいので、下の条件分岐と独立に考えてよい)
            ans = max(ans, dp[i][j] + Dishes[i - 1][1])

            # i 番目の料理を食べて j 分になることが可能なとき
            # (この条件を満たさないなら、i 番目の料理を食うと j 分以内に収まらない)
            if j - Dishes[i - 1][0] >= 0:
                dp[i][j] = max(dp[i][j],
                               dp[i - 1][j - Dishes[i - 1][0]] + Dishes[i - 1][1])
    return ans

print(e_all_you_can_eat())

Fixed submission:
def e_all_you_can_eat():
    N, T = [int(i) for i in input().split()]
    Dishes = sorted([[int(i) for i in input().split()] for j in range(N)])

    # dp[i][j]: i 番目までの料理を j 分以内に完食できるように選んだとき、満足度の和の最大値
    dp = [[0] * (T + 1) for _ in range(N + 1)]
    ans = 0
    dp[0][0] = 0  # 食べていないときの満足度は 0 とする
    for i in range(1, N + 1):
        for j in range(T):
            dp[i][j] = dp[i - 1][j]  # i 番目を食べなかった場合

            # i 番目を食べることにした場合
            # (最後の料理は、ラストオーダー時刻が来ていなければ
            # 頼んで食いっぱなしにしてよいので、下の条件分岐と独立に考えてよい)
            ans = max(ans, dp[i][j] + Dishes[i - 1][1])

            # i 番目の料理を食べて j 分になることが可能なとき
            # (この条件を満たさないなら、i 番目の料理を食うと j 分以内に収まらない)
            if j - Dishes[i - 1][0] >= 0:
                dp[i][j] = max(dp[i][j],
                               dp[i - 1][j - Dishes[i - 1][0]] + Dishes[i - 1][1])
    return ans

print(e_all_you_can_eat())
Buggy python submission (verdict: Runtime Error):
def d_disjoint_set_of_common_divisors():
    from math import gcd
    A, B = [int(i) for i in input().split()]

    def prime_factorization_dict(n):
        """nを素因数分解したときの素数とその指数の辞書"""
        from collections import defaultdict
        if n == 1:
            return {2: 0}  # 1は素数の0乗の積とみなす
        i, table = 2, defaultdict(int)
        while i**2 <= n:
            while n % i == 0:
                table[i] += 1
                n //= i
            i += 1
        if n > 1:
            table[n] = 1
        return table
    g = gcd(A, B)
    return len(prime_factorization_dict(g).keys()) + 1 if g > 1 else 1

print(d_disjoint_set_of_common_divisors())

Fixed submission:
def d_disjoint_set_of_common_divisors():
    A, B = [int(i) for i in input().split()]
    if A == 1 or B == 1:
        return 1

    def prime_factorization_dict(n):
        """nを素因数分解したときの素数の辞書"""
        from collections import defaultdict
        if n == 1:
            return {2: 0}  # 1は素数の0乗の積とみなす
        i, table = 2, defaultdict(int)
        while i**2 <= n:
            while n % i == 0:
                table[i] += 1
                n //= i
            i += 1
        if n > 1:
            table[n] = 1
        return set(table.keys())
    a_primekey = prime_factorization_dict(A)
    b_primekey = prime_factorization_dict(B)
    ans = []
    for a in a_primekey:
        if a in b_primekey:
            ans.append(a)
    return len(ans) + 1

print(d_disjoint_set_of_common_divisors())
Buggy python submission (verdict: Time Limit Exceeded):
def e_get_everything(INF=float('inf')):
    # 参考: http://drken1215.hatenablog.com/entry/2019/09/29/103500
    N, M = [int(i) for i in input().split()]
    A, B, C = [], [], []
    for _ in range(M):
        a, b = [int(i) for i in input().split()]
        A.append(a)
        B.append(b)
        # 開けられる宝箱の集合Cはビット列に変換しておく
        C.append(sum(1 << (t - 1) for t in [int(i) for i in input().split()]))

    # dp[i][S]: i番目まで(i番は含まない)の鍵からいくつか選んで、
    # 開いた宝箱の集合がS(ビット列で表す)で表されるような場合にかかる費用の最小値
    dp = [[INF] * (1 << N) for _ in range(M + 1)]
    dp[0][0] = 0  # 鍵を選ばず、開ける宝箱がないとき、費用は0とする

    for i in range(M):
        for j in range(1 << N):
            # i番目の鍵を使わない場合
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
            # i番目の鍵を使う場合
            next_j = j | C[i]  # C[i] で指定される宝箱(のいくつか)が新たに開く
            dp[i + 1][next_j] = min(dp[i + 1][next_j], dp[i][j] + A[i])
    # M個の鍵を使ってすべての宝箱を開けるとき、費用が有限値に更新されたか？
    return dp[M][(1 << N) - 1] if dp[M][(1 << N) - 1] != INF else -1

print(e_get_everything())

Fixed submission:
def e_get_everything(INF=float('inf')):
    # 参考: http://drken1215.hatenablog.com/entry/2019/09/29/103500
    N, M = [int(i) for i in input().split()]
    A, B, C = [], [], []
    for _ in range(M):
        a, b = [int(i) for i in input().split()]
        A.append(a)
        B.append(b)
        # 開けられる宝箱の集合Cはビット列に変換しておく
        C.append(sum(1 << (t - 1) for t in [int(i) for i in input().split()]))

    # dp[i][S]: i番目まで(i番は含まない)の鍵からいくつか選んで、
    # 開いた宝箱の集合がS(ビット列で表す)で表されるような場合にかかる費用の最小値
    dp = [[INF] * (1 << N) for _ in range(M + 1)]
    dp[0][0] = 0  # 鍵を選ばず、開ける宝箱がないとき、費用は0とする

    for i in range(M):
        for j in range(1 << N):
            # i番目の鍵を使わない場合
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
            # i番目の鍵を使う場合
            next_j = j | C[i]  # C[i] で指定される宝箱(のいくつか)が新たに開く
            dp[i + 1][next_j] = min(dp[i + 1][next_j], dp[i][j] + A[i])
    # M個の鍵を使ってすべての宝箱を開けるとき、費用が有限値に更新されたか？
    return dp[M][(1 << N) - 1] if dp[M][(1 << N) - 1] != INF else -1

print(e_get_everything())
Buggy python submission (verdict: Time Limit Exceeded):
def e_who_says_a_pun():
    N = int(input())
    S = input()

    def z_algorithm(string):
        n = len(string)
        ret = [0] * n
        i, j = 1, 0
        while i < n:
            while i + j < n and string[j] == string[i + j]:
                j += 1
            ret[i] = j
            if j == 0:
                i += 1
                continue
            k = 1
            while i + k < n and k + ret[k] < j:
                ret[i + k] = ret[k]
                k += 1
            i += k
            j -= k
        return ret

    ans = 0
    for i in range(N):
        t = S[i:N]
        lcp = z_algorithm(t)  # Longest Common Prefix
        for j in range(len(t)):
            ans = max(ans, min(lcp[j], j))
    return ans

print(e_who_says_a_pun())

Fixed submission:
def e_who_says_a_pun():
    N = int(input())
    S = input()

    def z_algorithm(string):
        n = len(string)
        ret = [0] * n
        i, j = 1, 0
        while i < n:
            while i + j < n and string[j] == string[i + j]:
                j += 1
            ret[i] = j
            if j == 0:
                i += 1
                continue
            k = 1
            while i + k < n and k + ret[k] < j:
                ret[i + k] = ret[k]
                k += 1
            i += k
            j -= k
        return ret

    ans = 0
    for i in range(N):
        t = S[i:N]
        lcp = z_algorithm(t)  # Longest Common Prefix
        for j in range(len(t)):
            ans = max(ans, min(lcp[j], j))
    return ans

print(e_who_says_a_pun())
Buggy python submission (verdict: Runtime Error):
def d_face_produces_unhappiness():
    N, K = [int(i) for i in input().split()]
    S = input()
    before_char = S[0]
    t = []
    v = 0
    for s in S + '*':
        if s != before_char:
            t.append(v)
            v = 1
        else:
            v += 1
        before_char = s
    t.sort(reverse=True)
    for i in range(K):
        t[i] += 2
    return min(sum([e - 1 for e in t]), N - 1)

print(d_face_produces_unhappiness())

Fixed submission:
def d_face_produces_unhappiness():
    N, K = [int(i) for i in input().split()]
    S = input()
    before_char = S[0]
    t = []
    v = 0
    for s in S + '*':
        if s != before_char:
            t.append(v)
            v = 1
        else:
            v += 1
        before_char = s
    t.sort(reverse=True)
    for i in range(min(K, len(t))):
        t[i] += 2
    return min(sum([e - 1 for e in t]), N - 1)

print(d_face_produces_unhappiness())
Buggy python submission (verdict: Runtime Error):
N = int(input())
P = [int(i) for i in input().split()]

permulated = len(1 for k, p in enumerate(P, 1) if p != k)
print('YES' if permulated <= 2 else 'NO')  

Fixed submission:
N = int(input())
P = [int(i) for i in input().split()]
p_sorted = list(sorted(P))

if P == p_sorted:
    print('YES')
    exit()
for i in range(N):
    for j in range(i + 1, N):
        P[i], P[j] = P[j], P[i]
        if P == p_sorted:
            print('YES')
            exit()
        P[i], P[j] = P[j], P[i]
print('NO')
Buggy python submission (verdict: Time Limit Exceeded):
def d_digits_parade(S, MOD=10**9 + 7):
    modulo = 13  # 13で割ったあまりを考えている
    # editorialでは2次元配列を考えているが、こうするとメモリを節約できる
    dp = [0] * modulo  # dp[k]: 13で割ったあまりがkの場合の数
    dp[0] = 1  # 初期値を0とすると、これを13で割ったあまりは0

    # Sを下の桁から見ていく
    # ex. 1?2?3: 0 - 3 - ?3 - 2?3 - ...

    mul = 1
    for c in S[::-1]:
        dp_next = [0] * modulo
        if c == '?':
            for k in range(10):  # ?に対し1桁の数字のすべてを試す
                for j in range(modulo):
                    # k * mul: mulの位がk、j: それより下の桁についてのあまり
                    # なので、このような遷移
                    dp_next[(k * mul + j) % modulo] += dp[j]
                    dp_next[(k * mul + j) % modulo] %= MOD
        else:
            k = int(c)
            for j in range(modulo):
                dp_next[(k * mul + j) % modulo] += dp[j]
                dp_next[(k * mul + j) % modulo] %= MOD
        # a*10**d % modulo = (a*(10**d % modulo)) % modulo なので、先に剰余を取る
        mul = (mul * 10) % modulo
        dp = dp_next
    return dp[5]

S = input()
print(d_digits_parade(S))

Fixed submission:
def d_digits_parade(S, MOD=10**9 + 7):
    modulo = 13  # 13で割ったあまりを考えている
    # editorialでは2次元配列を考えているが、こうするとメモリを節約できる
    dp = [0] * modulo  # dp[k]: 13で割ったあまりがkの場合の数
    dp[0] = 1  # 初期値を0とすると、これを13で割ったあまりは0

    # Sを下の桁から見ていく
    # ex. 1?2?3: 0 - 3 - ?3 - 2?3 - ...
    mul = 1
    for c in S[::-1]:
        dp_next = [0] * modulo
        if c == '?':
            for k in range(10):  # ?に対し1桁の数字のすべてを試す
                for j in range(modulo):
                    # k * mul: mulの位がk、j: それより下の桁についてのあまり
                    # なので、このような遷移
                    dp_next[(k * mul + j) % modulo] += dp[j]
                    dp_next[(k * mul + j) % modulo] %= MOD
        else:
            k = int(c)
            for j in range(modulo):
                dp_next[(k * mul + j) % modulo] += dp[j]
                dp_next[(k * mul + j) % modulo] %= MOD
        # a*10**d % modulo = (a*(10**d % modulo)) % modulo なので、先に剰余を取る
        # (多倍長整数を持ち出さなくてよくなる)
        mul = (mul * 10) % modulo
        dp = dp_next
    return dp[5]

S = input()
print(d_digits_parade(S))
Buggy python submission (verdict: Runtime Error):
def d_preparing_boxes(N, A):
    balls = [0] * N

    for i in range(N, 0, -1):
        t = i
        while t <= N:
            if balls[i - 1] % 2 != A[i - 1]:
                balls[i - 1] += 1
            t += i
    ans = [k for k, b in enumerate(balls, 1) if b != 0]
    return '\n'.join(map(str, (len(ans), *ans))) if len(ans) != 0 else 0

N = int(input())
A = [int(i) for i in input().split()]
print(d_preparing_boxes(N, A))

Fixed submission:
def d_preparing_boxes(N, A):
    boxes = [0] * (N + 1)
    result = []

    for i in range(N, 0, -1):
        # N以下のiの倍数(i自身を除く)の箱に入っているボールの数を求める
        total = 0
        for j in range(1, N // i):
            total += boxes[(j + 1) * i]
        # 求めたボール数と条件の偶奇が一致しないなら、i番の箱にボールを入れる
        if total % 2 != A[i - 1]:
            boxes[i] = 1
            result.append(i)
    return '\n'.join(map(str, [len(result)] + result)) if len(result) != 0 else 0

N = int(input())
A = [int(i) for i in input().split()]
print(d_preparing_boxes(N, A))
Buggy python submission (verdict: Runtime Error):
def e_virus_tree_2(N, K, Edges, MOD=10**9 + 7):
    graph = [[] for _ in range(N)]
    for a, b in Edges:
        graph[b - 1].append(a - 1)
        graph[a - 1].append(b - 1)

    def dfs(color, graph, current, parent):
        can_use_color_num = K - 1 if parent == -1 else K - 2

        if color < len(graph[current]):
            return 0  # 塗らねばならない子の数に対して色が足りない

        # コンビネーションの計算はここで行っている
        case_num = 1
        for child in graph[current]:
            if child == parent:
                continue
            case_num *= can_use_color_num
            case_num %= MOD
            can_use_color_num -= 1
        for child in graph[current]:
            if child == parent:
                continue
            case_num *= dfs(color, graph, child, current)
            case_num %= MOD
        return case_num

    ans = K * dfs(K, graph, 0, -1)
    return ans % MOD

N, K = [int(i) for i in input().split()]
Edges = [[int(i) for i in input().split()] for j in range(N - 1)]
print(e_virus_tree_2(N, K, Edges))

Fixed submission:
def e_virus_tree_2(N, K, Edges, MOD=10**9 + 7):
    import sys
    sys.setrecursionlimit(10**6)
    
    graph = [[] for _ in range(N)]
    for a, b in Edges:
        graph[b - 1].append(a - 1)
        graph[a - 1].append(b - 1)

    def dfs(color, graph, current, parent):
        can_use_color_num = K - 1 if parent == -1 else K - 2

        if color < len(graph[current]):
            return 0  # 塗らねばならない子の数に対して色が足りない

        # コンビネーションの計算はここで行っている
        case_num = 1
        for child in graph[current]:
            if child == parent:
                continue
            case_num *= can_use_color_num
            case_num %= MOD
            can_use_color_num -= 1
        for child in graph[current]:
            if child == parent:
                continue
            case_num *= dfs(color, graph, child, current)
            case_num %= MOD
        return case_num

    ans = K * dfs(K, graph, 0, -1)
    return ans % MOD

N, K = [int(i) for i in input().split()]
Edges = [[int(i) for i in input().split()] for j in range(N - 1)]
print(e_virus_tree_2(N, K, Edges))
Buggy python submission (verdict: Time Limit Exceeded):
def f_small_products(N, K, MOD=10**9 + 7):
    # 参考: https://atcoder.jp/contests/abc132/submissions/6187073
    sqrt_n = int(N**0.5)

    # num: 0 <= i <= Nについて、N // i の値で同一視できるものの個数が前から格納される
    num = [0 for i in range(2 * sqrt_n + 1)]
    # 1から√N までは、同一視できるものの個数は1つ
    for i in range(1, sqrt_n + 1):
        num[i] = 1
    # √NからN までは、複数の整数が同一視されることがある
    for i in range(1, sqrt_n + 1):
        lo = max(sqrt_n + 1, (N + i + 1) // (i + 1))
        hi = N // i
        num[2 * sqrt_n + 1 - i] = hi - lo + 1

    # dp[n][m]: 最後の整数が m であるような n 個の整数を
    # 並べて条件を満たすようにする場合の数
    dp = [[0 for j in range(2 * sqrt_n + 2)] for i in range(K + 1)]
    dp[0][1] = 1  # 数列の先頭のさらに1個前に1があるとみなす(置き方1通り)
    for i in range(K):
        # 累積和を用いたdpテーブルの更新(imos法)
        for j in range(1, 2 * sqrt_n + 1):
            ways = (dp[i][j] * num[j]) % MOD
            dp[i + 1][1] += ways
            dp[i + 1][2 * sqrt_n + 2 - j] -= ways
        for j in range(1, 2 * sqrt_n + 1):
            dp[i + 1][j] += dp[i + 1][j - 1]

    return sum(a * b for a, b in zip(dp[K], num)) % MOD

N, K = [int(i) for i in input().split()]
print(f_small_products(N, K))

Fixed submission:
def f_small_products(N, K, MOD=10**9 + 7):
    # 参考: https://atcoder.jp/contests/abc132/submissions/6187073
    sqrt_n = int(N**0.5)

    # num: 0 <= i <= Nについて、N // i の値で同一視できるものの個数が前から格納される
    num = [0 for i in range(2 * sqrt_n + 1)]
    # 1から√N までは、同一視できるものの個数は1つ
    for i in range(1, sqrt_n + 1):
        num[i] = 1
    # √NからN までは、複数の整数が同一視されることがある
    for i in range(1, sqrt_n + 1):
        lo = max(sqrt_n + 1, (N + i + 1) // (i + 1))
        hi = N // i
        num[2 * sqrt_n + 1 - i] = hi - lo + 1

    # dp[n][m]: 最後の整数が m であるような n 個の整数を
    # 並べて条件を満たすようにする場合の数
    dp = [[0 for j in range(2 * sqrt_n + 2)] for i in range(K + 1)]
    dp[0][1] = 1  # 数列の先頭のさらに1個前に1があるとみなす(置き方1通り)
    for i in range(K):
        # 累積和を用いたdpテーブルの更新(imos法)
        for j in range(1, 2 * sqrt_n + 1):
            ways = (dp[i][j] * num[j]) % MOD
            dp[i + 1][1] += ways
            dp[i + 1][2 * sqrt_n + 2 - j] -= ways
        for j in range(1, 2 * sqrt_n + 1):
            dp[i + 1][j] += dp[i + 1][j - 1]

    return sum(a * b for a, b in zip(dp[K], num)) % MOD

N, K = [int(i) for i in input().split()]
print(f_small_products(N, K))