Problem p03253 (python)

Fixed submission:
import sys
import math
input = sys.stdin.readline

def factorization(num):
    MAX_PRIME = int(math.sqrt(num)) + 1
    primes = []
    is_prime = [True] * (MAX_PRIME+1)
    for i in range(2, MAX_PRIME+1):
        if is_prime[i]:
            primes.append(i)
            for j in range(2*i, MAX_PRIME+1, i):
                is_prime[j] = False
    insu = []
    tmp = num
    max_count = 0
    for i in range(len(primes)):
        count = 0
        while tmp%primes[i] == 0:
            tmp //= primes[i]
            count += 1
        if count > 0:
            insu.append((primes[i], count))
            max_count = max(max_count, count)
        if tmp == 1:
            break
    if tmp != 1:
        insu.append((tmp, 1))
    return insu, max_count

def main():
    N, M = map(int, input().split())

    MOD = int(1e9) + 7

    insu, max_count = factorization(M)
    
    kai = [1] * (max_count + N)
    for i in range(1, max_count + N):
        kai[i] = (kai[i-1] * i) % MOD
    
    ans = 1
    tmp = pow(kai[N-1], MOD-2, MOD)
    for prime, count in insu:
        ans *= kai[count + N - 1] * tmp * pow(kai[count], MOD-2, MOD)
        ans %= MOD
    print(ans)

if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
import math
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())

    MOD = int(1e9) + 7

    kai = [1] * (N+1)
    for i in range(2, N+1):
        kai[i] = kai[i-1] * i
        kai[i] %= MOD

    MAX_PRIME = int(math.sqrt(M)) + 1
    primes = []
    is_prime = [True] * (MAX_PRIME+1)
    for i in range(2, MAX_PRIME+1):
        if is_prime[i]:
            primes.append(i)
            for j in range(2*i, MAX_PRIME+1, i):
                is_prime[j] = False
    
    insu = []

    tmp = M
    max_count = 0
    for i in range(len(primes)):
        count = 0
        while tmp%primes[i] == 0:
            tmp //= primes[i]
            count += 1
        if count > 0:
            insu.append((primes[i], count))
            max_count = max(max_count, count)
    # print(insu)
    
    max_c = min(max_count, N)
    n_c = [1] * (max_c + 1)

    for i in range(1, max_c+1):
        n_c[i] = kai[N] * pow(kai[N-i], MOD-2, MOD) * pow(kai[i], MOD-2, MOD)

    ans = 1
    for p, c in insu:
        # print(p, c)
        tmp = 0
        for i in range(1, min(max_c, c)+1):
            tmp += n_c[i] * kai[c-1] * pow(kai[c-i], MOD-2, MOD) * pow(kai[i-1], MOD-2, MOD)
            tmp %= MOD
        if tmp > 0:
            ans *= tmp
            ans %= MOD
    print(ans)

if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
import math
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())

    MOD = int(1e9) + 7

    kai = [1] * (N+1)
    for i in range(2, N+1):
        kai[i] = kai[i-1] * i
        kai[i] %= MOD

    MAX_PRIME = int(math.sqrt(M)) + 1
    primes = []
    is_prime = [True] * (MAX_PRIME+1)
    for i in range(2, MAX_PRIME+1):
        if is_prime[i]:
            primes.append(i)
            for j in range(2*i, MAX_PRIME+1, i):
                is_prime[j] = False
    
    insu = []

    tmp = M
    max_count = 0
    for i in range(len(primes)):
        count = 0
        while tmp%primes[i] == 0:
            tmp //= primes[i]
            count += 1
        if count > 0:
            insu.append((primes[i], count))
            max_count = max(max_count, count)
    # print(insu)
    
    max_c = min(max_count, N)
    n_c = [1] * (max_c + 1)

    for i in range(1, max_c+1):
        n_c[i] = kai[N] * pow(kai[N-i], MOD-2, MOD) * pow(kai[i], MOD-2, MOD)

    ans = 1
    for p, c in insu:
        # print(p, c)
        tmp = 0
        for i in range(1, min(max_c, c)+1):
            tmp += n_c[i] * kai[c-1] * pow(kai[c-i], MOD-2, MOD) * pow(kai[i-1], MOD-2, MOD)
            tmp %= MOD
        ans *= tmp
        ans %= MOD
    print(ans)

if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
import math
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())

    MOD = int(1e9) + 7

    kai = [1] * (N+1)
    for i in range(2, N+1):
        kai[i] = kai[i-1] * i
        kai[i] %= MOD

    MAX_PRIME = int(math.sqrt(M)) + 1
    primes = []
    is_prime = [True] * (MAX_PRIME+1)
    for i in range(2, MAX_PRIME+1):
        if is_prime[i]:
            primes.append(i)
            for j in range(2*i, MAX_PRIME+1, i):
                is_prime[j] = False
    
    insu = []

    tmp = M
    max_count = 0
    for i in range(len(primes)):
        count = 0
        while tmp%primes[i] == 0:
            tmp //= primes[i]
            count += 1
        if count > 0:
            insu.append((primes[i], count))
            max_count = max(max_count, count)
    # print(insu)
    
    max_c = min(max_count, N)
    n_c = [1] * (max_c + 1)

    for i in range(1, max_c+1):
        n_c[i] = kai[N] * pow(kai[N-i], MOD-2, MOD) * pow(kai[i], MOD-2, MOD)

    ans = 1
    for p, c in insu:
        tmp = 0
        for i in range(1, c+1):
            tmp += n_c[i] * kai[c-1] * pow(kai[c-i], MOD-2, MOD) * pow(kai[i-1], MOD-2, MOD)
            tmp %= MOD
        ans *= tmp
        ans %= MOD
    print(ans)

if __name__ == "__main__":
    main()