Problem:


Score : 400 points

Problem Statement

You are given positive integers N and M.

How many sequences a of length N consisting of positive integers satisfy a_1 \times a_2 \times ... \times a_N = M? Find the count modulo 10^9+7.

Here, two sequences a' and a'' are considered different when there exists some i such that a_i' \neq a_i''.

Constraints

All values in input are integers.

1 \leq N \leq 10^5

1 \leq M \leq 10^9

Input

Input is given from Standard Input in the following format:

N M

Output

Print the number of the sequences consisting of positive integers that satisfy the condition, modulo 10^9 + 7.

Sample Input 1

2 6

Sample Output 1

4

Four sequences satisfy the condition: \{a_1, a_2\} = \{1, 6\}, \{2, 3\}, \{3, 2\} and \{6, 1\}.

Sample Input 2

3 12

Sample Output 2

18

Sample Input 3

100000 1000000000

Sample Output 3

957870001



Sample input:
2 6


Sample output:
4

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3


import array
import collections
import functools
import math
import random


M = 10 ** 9 + 7


def sieve_of_eratosthenes(end, typecode="L"):
    """Enumerates the prime numbers below the given integer.
    :param int end: Prime numbers below this integer will be enumerated.
    :param str typecode: The type of the array to be returned (optional).
    :return: The array of the prime numbers.
    :rtype: :class:`array.array`
    """

    assert end > 1
    is_prime = array.array("B", (True for i in range(end)))
    is_prime[0] = False
    is_prime[1] = False
    primes = array.array(typecode)
    for i in range(2, end):
        if is_prime[i]:
            primes.append(i)
            for j in range(2 * i, end, i):
                is_prime[j] = False
    return primes


def factorize_trial_division(n, typecode="L"):
    """Factorizes the given integer in prime numbers by trial division.
    :param int n: The integer to be factorized.
    :param str typecode: The type of the array to be returned (optional).
    :return: The array of factors.
    :rtype: :class:`array.array`
    """
    factors = array.array(typecode)
    if n < 2:
        return factors
    for p in sieve_of_eratosthenes(math.ceil(math.sqrt(n)) + 1):
        if p * p > n:
            break
        while n % p == 0:
            factors.append(p)
            n //= p
    if n > 1:
        factors.append(n)
    return factors


def is_prime_miller_rabin(n, k=50):
    """Determing whether the given integer is prime by the Miller-Rabin test.
    :param int n: The integer to be checked.
    :param int k: The parameter representing the accuracy of the determination.
    :return: Whether n is prime or not.
    :rtype: bool
    """
    assert n > 0
    if n == 2:
        return True
    elif n == 1 or n % 2 == 0:
        return False
    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1
    for _ in range(k):
        a = random.randint(1, n - 1)
        if pow(a, d, n) != 1:
            for r in range(0, s):
                if pow(a, d * 2 ** r, n) == n - 1:
                    break
            else:
                return False
    return True


class ModPrime(object):

    def __init__(self, max_n=1000000, mod=M):
        # cf. http://hos.ac/slides/20130319_enumeration.pdf
        self.max_n = max_n
        assert is_prime_miller_rabin(mod)
        self.mod = mod
        self.invs = [None, 1]
        for i in range(2, self.max_n + 1):
            self.invs.append(mod - mod // i * self.invs[mod % i] % mod)
        self.facts = [1]
        self.fact_invs = [1]
        for i in range(1, self.max_n + 1):
            self.facts.append(self.facts[i - 1] * i % mod)
            self.fact_invs.append(self.fact_invs[i - 1] * self.invs[i] % mod)
    
    def inv(self, n):
        return self.invs[n]
    
    def fact(self, n):
        return self.facts[n]
    
    def fact_inv(self, n):
        return self.fact_invs[n]
    
    def comb(self, n, r):
        if r < 0 or r > n:
            return 0
        return self.fact(n) * self.fact_inv(r) % self.mod * self.fact_inv(n - r) % self.mod
    
    def multi_choose(self, n, r):
        return self.comb(n + r - 1, r)


def mod_prod(xs, mod=M):
    return functools.reduce(lambda x, y: x * y % mod, xs) % mod


def solve(n, m, mod=M):
    fs = collections.Counter(factorize_trial_division(m))
    mp = ModPrime(mod=M)
    res = mod_prod((mp.multi_choose(n, v) for v in fs.values()), mod=M)
    return res


def main():
    n, m = (int(z) for z in input().split())
    res = solve(n, m)
    print(res)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N,M = map(int, input().split())
mod = 10 ** 9 + 7

def primes_sieve(n):
    sieve = [True] * (n + 1)
    for i in range(2, n + 1):
        if sieve[i]:
            for j in range(i + i, n + 1, i):
                sieve[j] = False
    return [i for i, x in enumerate(sieve[2:], 2) if x]

import math
primes = primes_sieve(int(math.sqrt(10**9)))

ps = []
t = M
for p in primes:
    u = 0
    while True:
        d, m = divmod(t, p)
        if m == 0:
            u += 1
            t = d
        else:
            break
    if u != 0:
        ps.append((p, u))

import itertools, operator
class GFp:
    def __init__(self, p):
        self.p = p
    def inv(self, v):
        return pow(v, self.p - 2, self.p)

class CachedComb:
    def __init__(self, n, mod):
        self.mod = mod
        self.gfp = GFp(mod)

        self.n = n
        self.fact_cache = list(
                itertools.accumulate(
                        itertools.chain(
                                [1],
                                range(1, n+1)
                        ),
                        operator.mul
                )
        )
    def comb(self, n, m):
        if n < m: return 0
        if m == 0 or n == m: return 1
        return self.fact_cache[n] * self.gfp.inv(
                self.fact_cache[n - m] * self.fact_cache[m]
        ) % mod

cc = CachedComb(N + max(x[1] for x in ps), mod)

ans = 1
for p, c in ps:
    cmb = cc.comb(c + N - 1, N - 1)
    ans = ans * cmb
print(ans)

Submission status: Runtime Error

Solution code:
import sympy
import math

N, M = map(int, input().split())
factors = sympy.factorint(M)
print(factors)
num_pattern = 1;
for exponent in factors.values():
    if exponent < N:
        tmp_num_pattern = int(math.factorial(exponent + N -1) \
                            / (math.factorial(N-1)*math.factorial(exponent)))
    else:
        tmp_num_pattern = int(math.factorial(exponent + N -1) \
                            / (math.factorial(exponent)*math.factorial(N-1)))
        
    num_pattern = num_pattern * int(tmp_num_pattern)
print(int(num_pattern%(10**9 +7)))

Submission status: Runtime Error

Solution code:
# encoding: utf-8
import math, random
N, M = map(int, input().split())

def distribute(pos, full, tmp):
    return memo[tmp][pos]

def f1(x, c, n):
    return (x ** 2 + c) % n

def gcd(a, b):
    if b < 1: return a
    else: return gcd(b, a % b)

def pra(n, c):
    # print("######", n, c)
    if n % 2 == 0: return 2
    elif prime(n) == True: return n
    x = y = 2
    d = 1
    while d == 1:
        x = f1(x, c, n)
        y = f1(f1(y, c, n), c, n)
        d = gcd(n, int(math.fabs(x - y)))
    return pra(d, c + 1)
    
def jaeschke(n):
    d2s = n - 1
    for s in range(1, 32):
        if d2s % (2 ** (s + 1)) > 0: break
    d = d2s // (2 ** s)
    # print("###", n, d, s)
    for a in (2, 7, 61): 
        if (a ** d) % n == 1: continue
        for r in range(s):
            if (a ** (d * (2 ** r))) % n == n - 1: break
        else:
            return False
    else:
        return True

def prime(n):
    # print("####", n)
    if n == 2: return True
    elif n % 2 == 0: return False
    else: return jaeschke(n)

def pf(X):
    X_tmp = X
    ips = []
    c = 1
    for i in range(32):
        for c in range(1, 2):
            d = pra(X_tmp, c)
            if d > -1: break
        # print("##", X_tmp, d, c)
        for i_p in range(1, 32):
            if X_tmp % (d ** (i_p + 1)) > 0: break
        # print("#", X_tmp, d, i_p)
        X_tmp = X_tmp // (d ** i_p)
        ips.append(i_p)
        if X_tmp == 1: break
    else:
        # print("#", X_tmp, X_tmp, 1)
        ips.append(1)
    return ips

ips = pf(M)
    
#### O(NlogM) below ?
# create memo
## init
if len(ips) > 0: ip_max = max(ips)
else: ip_max = 0
memo = [[None] * N for i in range(ip_max + 1)] # max ip
for j in range(N): memo[0][j] = 1
for i in range(1, ip_max + 1): memo[i][N - 1] = 1
## fill
for i in range(1, ip_max + 1):
    sum_tmp = 0
    vals = list(memo[i - 1])[::-1]
    p_memo = memo[i]
    for j, val in enumerate(vals):
        sum_tmp += val
        p_memo[N - 1 - j] = sum_tmp
#### O(NlogM) above ?
        
# calculate ans
ans = 1
for i_p in ips: ans = (ans * distribute(0, i_p, i_p)) % (10 ** 9 + 7)

if M == 1: print(1)
elif ip_max < 1: print(N)
else: print(ans)

Submission status: Runtime Error

Solution code:
# encoding: utf-8
import math, random
N, M = map(int, input().split())

def distribute(pos, full, tmp):
    return memo[tmp][pos]

# # define search range
# p_max = M // 2 # M is prime if M has a factor p (> p_max)
# ip_up = max((1, int(math.log2(M)))) # MDE
#
# #### O(MlogM) below (if M has a very large prime factor)
# M_tmp = M
# ips = []
# for p in range(2, p_max + 1):
#     if M_tmp % p > 0: continue
#     # how many times M_tmp can be divided
#     p_tmp = p
#     for i_p in range(ip_up + 1):
#         if M_tmp % p_tmp > 0: break
#         p_tmp = p_tmp * p
#     # calculate later
#     ips.append(i_p)
#     # next
#     M_tmp = M_tmp // (p_tmp // p)
#     if M_tmp == 1: break
# #### O(Mlog M) above

def lcg(x, c, n):
    return (x ** 2 + c) % n

def gcd(a, b):
    if b < 1: return a
    else: return gcd(b, a % b)

def pra(n, c):
    # print("######", n, c)
    x = y = 2
    d = 1
    while d == 1:
        x = lcg(x, c, n)
        y = lcg(lcg(y, c, n), c, n)
        d = gcd(n, int(math.fabs(x - y)))
        # print("#####", x, y, d)
    if prime(d) == True: return d
    elif d % 2 == 0: return 2 # prime factor 2 cannot be found ?
    elif d == n: return pra(n, c + 1)
    else: return pra(d, 1)
    
def jaeschke(n):
    d2s = n - 1
    for s in range(1, 32):
        if d2s % (2 ** (s + 1)) > 0: break
    d = d2s // (2 ** s)
    # print("###", n, d, s)
    for a in (2, 7, 61): 
        if (a ** d) % n == 1: continue
        for r in range(s):
            if (a ** (d * (2 ** r))) % n == n - 1: break
        else:
            return False
    else:
        return True

def prime(n):
    # print("####", n)
    if n == 2: return True
    elif n % 2 == 0: return False
    else: return jaeschke(n)

def pf(X):
    X_tmp = X
    ips = []
    c = 1
    for i in range(32):
        d = pra(X_tmp, c)
        # print("##", X_tmp, d, c)
        for i_p in range(1, 32):
            if X_tmp % (d ** (i_p + 1)) > 0: break
        # print("#", X_tmp, d, i_p)
        X_tmp = X_tmp // (d ** i_p)
        ips.append(i_p)
        if X_tmp == 1: break
    else:
        # print("#", X_tmp, X_tmp, 1)
        ips.append(1)
    return ips

ips = pf(M)
    
#### O(NlogM) below ?
# create memo
## init
if len(ips) > 0: ip_max = max(ips)
else: ip_max = 0
memo = [[None] * N for i in range(ip_max + 1)] # max ip
for j in range(N): memo[0][j] = 1
for i in range(1, ip_max + 1): memo[i][N - 1] = 1
## fill
for i in range(1, ip_max + 1):
    sum_tmp = 0
    vals = list(memo[i - 1])[::-1]
    p_memo = memo[i]
    for j, val in enumerate(vals):
        sum_tmp += val
        p_memo[N - 1 - j] = sum_tmp
#### O(NlogM) above ?
        
# calculate ans
ans = 1
for i_p in ips: ans = (ans * distribute(0, i_p, i_p)) % (10 ** 9 + 7)

if M == 1: print(1)
elif ip_max < 1: print(N)
else: print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import math

mod = 10**9 + 7

n, m = map(int, input().split())

def factorization(n):
    d = defaultdict(int)
    if n == 1:
        return None
    else:
        for i in range(2, int(n**0.5)+2):
            if n % i == 0:
                tmp = 0
                while n%i == 0:
                    n = n//i
                    tmp += 1
                d[i] = tmp
        return d

def comb(n,m):
    return math.factorial(n) // (math.factorial(n-m) * math.factorial(m))

d = factorization(m)

ans = 1
for k,v in d.items():
    ans *= comb(v+n-1, v)
    ans %= mod

print(ans)

Submission status: Runtime Error

Solution code:
from sys import stdin


def prime_factorization(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n //= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table


def num_of_prime_factorization(n):
    i = 2
    table = []
    while i * i <= n:
        loop_num = 0
        while n % i == 0:
            n //= i
            loop_num += 1
            if n % i != 0:
                table.append(loop_num)
        i += 1
    return table


def factorial(n):
    if n > 1:
        return n * factorial(n - 1)
    else:
        return 1


N, M = [int(i) for i in stdin.readline().rstrip().split()]

lst = num_of_prime_factorization(M)
ans = 1

for b in lst:
    ans *= factorial(b + N - 1) // (factorial(b) * factorial(N - 1))

print(ans)

Submission status: Runtime Error

Solution code:
iN,iM = [int(x) for x in input().split()]
iD = 10**9 +7 #法

def fPrimeCounter(iM):
    iS = int(iM ** 0.5) + 1
    aRet = []
    for i in range(2,iS + 1):
        iCounter = 0
        while iM % i == 0:
            iM /= i
            iCounter += 1
        if 0 < iCounter : aRet.append(iCounter)
        if iM == 1 : break
    if 1 < iM  : aRet.append(1)
    return aRet
def fnCr(iN,iR,iD):
    iR = min(iR,iN-iR)
    if iR == 1 :
        return iN
    return (iN % iD) * pow(iR,iD-2,iD) * fnCr(iN-1,iR-1,iD) % iD

aP = fPrimeCounter(iM)
if aP == []:
    print(1)
    exit()
iRet = 1
for i in aP:
    # i + iN -1  C  iN -1
    iRet *= fnCr(i+iN-1,i,iD)
iRet %= iD
print(iRet)

Submission status: Runtime Error

Solution code:
iN,iM = [int(x) for x in input().split()]
iD = 10**9 +7 #法

def fPrimeCounter(iM):
    iS = int(iM ** 0.5) + 1
    aRet = []
    for i in range(2,iS + 1):
        iCounter = 0
        while iM % i == 0:
            iM = iM / i
            iCounter += 1
        if 0 < iCounter : aRet.append(iCounter)
        if iM == 1 : break
    if 1 < iM  : aRet.append(1)
    return aRet
def fnCr(iN,iR,iD):
    iR = min(iR,iN-iR)
    if iR == 1 :
        return iN
    return (iN % iD) * pow(iR,iD-2,iD) * fnCr(iN-1,iR-1,iD) % iD

aP = fPrimeCounter(iM)
if len(aP) == 0:
    print(1)
    exit()
iRet = 1
for i in aP:
    # i + iN -1  C  iN -1
    iRet *= fnCr(i+iN-1,iN-1,iD)
iRet %= iD
print(iRet)

Submission status: Runtime Error

Solution code:
iN,iM = [int(x) for x in input().split()]
iD = 10**9 +7 #法

def fPrimeCounter(iM):
    iS = int(iM ** 0.5) + 1
    aRet = []
    for i in range(2,iS + 1):
        iCounter = 0
        while iM % i == 0:
            iM = iM / i
            iCounter += 1
        if 0 < iCounter : aRet.append(iCounter)
        if iM == 1 : break
    if 1 < iM  : aRet.append(1)
    return aRet
def fnCr(iN,iR,iD):
    iR = min(iR,iN-iR)
    if iR == 1 :
        return iN
    return (iN % iD) * pow(iR,iD-2,iD) * fnCr(iN-1,iR-1,iD) % iD

aP = fPrimeCounter(iM)
if len(aP) == 0:
    print(1)
    exut()
iRet = 1
for i in aP:
    # i + iN -1  C  iN -1
    iRet *= fnCr(i+iN-1,iN-1,iD)
iRet %= iD
print(iRet)

Submission status: Runtime Error

Solution code:
iN,iM = [int(x) for x in input().split()]
iD = 10**9 +7 #法

def fPrimeCounter(iM):
    iS = int(iM ** 0.5) + 1
    aRet = []
    for i in range(2,iS + 1):
        iCounter = 0
        while iM % i == 0:
            iM = iM / i
            iCounter += 1
        if 0 < iCounter : aRet.append(iCounter)
        if iM == 1 : break
    if 1 < iM  : aRet.append(1)
    return aRet
def fnCr(iN,iR,iD):
    iR = min(iR,iN-iR)
    if iR == 1 :
        return iN
    return (iN % iD) * pow(iR,iD-2,iD) * fnCr(iN-1,iR-1,iD) % iD

aP = fPrimeCounter(iM)
iRet = 1
for i in aP:
    # i + iN -1  C  iN -1
    iRet *= fnCr(i+iN-1,iN-1,iD)
iRet %= iD
print(iRet)

Submission status: Runtime Error

Solution code:
import math
from scipy.special import comb
n,m = map(int,input().split(" "))

m2 = int(math.sqrt(m))
mod = 10**9+7

n_so = {}

for i in range(2,m2+2):
    t = 0
    while m%i == 0:
        m = int(m/i)
        t += 1
    if t > 0:
        n_so[i] = t
        if m == 1:
            break

ans = 1
su = n_so.values()

for i in su:
    ans = ans * comb(n-1+i,n-1,exact = True) % mod

print(ans%mod)

Submission status: Runtime Error

Solution code:

iN,iM = [int(x) for x in input().split()]
iD = 10**9 +7 #法

def fPrimeCounter(iM):
    iS = int(iM ** 0.5) + 1
    aRet = []
    for i in range(2,iS + 1):
        iCounter = 0
        while iM % i == 0:
            iM = iM / i
            iCounter += 1
        if 0 < iCounter : aRet.append(iCounter)
        if iM == 1 : break
    if 1 < iM  : aRet.append(1)
    return aRet

#二分累乗法 iDを法として
def fBiPow(iX,iN,iD):
    iY = 1
    while iN > 0:
        if iN % 2 == 0:
            iX = iX * iX % iD
            iN = iN // 2
        else:
            iY = iX * iY % iD
            iN = iN - 1
    return iY

aP = fPrimeCounter(iM)
iMax = max(aP) + iN - 1
aM = [1] * (iMax + 1)
#階乗 iD を法とした
for i in range(1,iMax + 1):
    aM[i] = aM[i-1] * i  % iD
aInvM = [1]* (iMax + 1)
aInvM[iMax] = fBiPow(aM[iMax],iD-2,iD)
#階乗の逆元 iD を法とした
for i in range(iMax,0,-1):
    aInvM[i-1] = aInvM[i]*i % iD

iRet = 1
for i in aP:
    # i + iN -1  C  iN -1
    iRet *= aM[i+iN-1] * aInvM[iN-1] * aInvM[i] % iD
iRet %= iD
print(iRet)

Submission status: Runtime Error

Solution code:


iN,iM = [int(x) for x in input().split()]
iD = 10**9 +7 #法

def fPrimeCounter(iM):
    iS = int(iM ** 0.5) + 1
    aRet = []
    for i in range(2,iS + 1):
        iCounter = 0
        while iM % i == 0:
            iM = iM / i
            iCounter += 1
        if 0 < iCounter : aRet.append(iCounter)
        if iM == 1 : break
    if 1 < iM  : aRet.apend(1)
    return aRet

#二分累乗法 iDを法として
def fBiPow(iX,iN,iD):
    iY = 1
    while iN > 0:
        if iN % 2 == 0:
            iX = iX * iX % iD
            iN = iN // 2
        else:
            iY = iX * iY % iD
            iN = iN - 1
    return iY

aP = fPrimeCounter(iM)
iMax = max(aP) + iN - 1
aM = [1] * (iMax + 1)
#階乗 iD を法とした
for i in range(1,iMax + 1):
    aM[i] = aM[i-1] * i  % iD
aInvM = [1]* (iMax + 1)
aInvM[iMax] = fBiPow(aM[iMax],iD-2,iD)
#階乗の逆元 iD を法とした
for i in range(iMax,0,-1):
    aInvM[i-1] = aInvM[i]*i % iD

iRet = 1
for i in aP:
    # i + iN -1  C  iN -1
    iRet *= aM[i+iN-1] * aInvM[iN-1] * aInvM[i] % iD
iRet %= iD
print(iRet)

Submission status: Runtime Error

Solution code:
import sys

MOD = 10 ** 9 + 7

def main():
    n, m = [int(s) for s in input().split()]
    print(solve(m, n))

def solve(m, n):
    factors = list(get_prime_factors(m))
    h = max(c for f, c in factors)

    table = dict()
    table[1] = [1 for _ in range(h + 1)]

    i = 1
    while i < n:
        j = n & (i - 1)
        table[i * 2] = [0 for _ in range(h + 1)]
        if n & i != 0 and j != 0:
            table[i + j] = [0 for _ in range(h + 1)]
        for x in range(h + 1):
            for y in range(h + 1 - x):
                table[i * 2][x + y] = (table[i * 2][x + y] + table[i][x] * table[i][y]) % MOD
                if n & i != 0 and j != 0:
                    table[i + j][x + y] = (table[i + j][x + y] + table[i][x] * table[j][y]) % MOD

        if n & i == 0:
            del table[i]
        if n & i != 0 and j != 0:
            del table[i]
            del table[j]

        i *= 2

    ans = 1
    for f, c in factors:
        ans = ans * table[n][c] % MOD
    return ans

def get_prime_factors(n):
    import itertools

    m = n
    for i in itertools.count(2):
        if i * i > m:
            break

        c = 0
        while True:
            x, y = divmod(m, i)
            if y != 0:
                break
            c += 1
            m = x
        if c != 0:
            yield i, c

    if m != 1:
        yield m, 1


main()

Submission status: Runtime Error

Solution code:
iN,iM = [int(x) for x in input().split()]
iD = 10**9 +7 #法

def fPrimeCounter(iM):
    i = 2
    iS = iM ** 0.5 + 1
    aRet = []
    while i < iS or i <= iM  :
        iCounter = 0
        while iM % i == 0:
            iM = iM // i
            iCounter += 1
        if 0 < iCounter : aRet.append(iCounter)
        i += 1
    return aRet

#ABC042Dの流用
#二分累乗法 iDを法として
def fBiPow(iX,iN,iD):
    iY = 1
    while iN > 0:
        if iN % 2 == 0:
            iX = iX * iX % iD
            iN = iN // 2
        else:
            iY = iX * iY % iD
            iN = iN - 1
    return iY

aP = fPrimeCounter(iM)
iMax = max(aP) + iN - 1
aM = [1] * (iMax + 1)
#階乗 iD を法とした
for i in range(1,iMax + 1):
    aM[i] = aM[i-1] * i  % iD
aInvM = [1]* (iMax + 1)
aInvM[iMax] = fBiPow(aM[iMax],iD-2,iD)
#階乗の逆元 iD を法とした
for i in range(iMax,0,-1):
    aInvM[i-1] = aInvM[i]*i % iD

iRet = 1
for i in aP:
    # i + iN -1  C  iN -1
    iRet *= aM[i+iN-1] * aInvM[iN-1] % iD * aInvM[i] % iD
iRet %= iD
print(iRet)

Submission status: Runtime Error

Solution code:
MOD = 10 ** 9 + 7

def main():
    n, m = [int(s) for s in input().split()]
    print(solve(m, n))

def solve(m, n):
    factors = list(get_prime_factors(m))
    h = max(c for f, c in factors)

    table = dict()
    table[1] = [1 for _ in range(h + 1)]

    i = 1
    while i < n:
        j = n & (i - 1)
        table[i * 2] = [0 for _ in range(h + 1)]
        if j != 0:
            table[i + j] = [0 for _ in range(h + 1)]
        for x in range(h + 1):
            for y in range(h + 1 - x):
                table[i * 2][x + y] = (table[i * 2][x + y] + table[i][x] * table[i][y]) % MOD
                if j != 0:
                    table[i + j][x + y] = (table[i + j][x + y] + table[i][x] * table[j][y]) % MOD
        i *= 2

    ans = 1
    for f, c in factors:
        ans = ans * table[n][c] % MOD
    return ans

def get_prime_factors(n):
    import itertools

    m = n
    for i in itertools.count(2):
        if i * i > m:
            break

        c = 0
        while True:
            x, y = divmod(m, i)
            if y != 0:
                break
            c += 1
            m = x
        if c != 0:
            yield i, c

    if m != 1:
        yield m, 1


main()

Submission status: Runtime Error

Solution code:
def framod(n,mod):
    a=1
    for i in range(1,n+1):
        a=a * i % mod
    return a

def power(n,r,mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod
    
def comb(n,k,mod):
    if n<0 or k<0 or n<k: return 0
    if n==0 or k==0: return 1
    a=framod(n,mod)
    b=framod(k,mod)
    c=framod(n-k,mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod

n,m=map(int, input().split())

pf={}
for i in range(2,int(m**0.5)+1):
    while m%i==0:
        pf[i]=pf.get(i,0)+1
        m//=i
if m>1:pf[m]=1
    
mblist=list()
for i in pf:
    a = comb(pf[i]+n-1,pf[i],mod)
    mblist.append(a)
ans=1
for i in mblist:
    ans=(ans*i)%mod
print(ans)

Submission status: Runtime Error

Solution code:
from math import floor, sqrt
from collections import Counter

MOD = 10 ** 9 + 7

# xを素因数分解する
def getPrimeFactor(x):
    ans = []
    for d in range(2, floor(sqrt(x)) + 1):
        while x % d == 0:
            ans.append(d)
            x //= d

    if x != 1:
        ans.append(x)

    return ans

# xのn乗（二分累乗法）
def power(x, n):
    ans = 1
    while n:
        if n % 2 == 1:
            ans = (ans * x) % MOD
        x = (x * x) % MOD
        n //= 2
    return ans


N, M = map(int, input().split())

PFs = getPrimeFactor(M)
cnt = Counter(PFs)

maxNum = max(cnt.values())
N2 = N + maxNum

# facts[x]: xの階乗
facts = [1] + [0] * N2
for x in range(1, N2 + 1):
    facts[x] = (facts[x - 1] * x) % MOD

# invFs[x]: xの階乗の逆元
invFs = [0] * N2 + [power(facts[N2], MOD - 2)]
for x in reversed(range(N2)):
    invFs[x] = (invFs[x + 1] * (x + 1)) % MOD

def comb(n, k):
    return ((facts[n] * invFs[k]) % MOD * invFs[n - k]) % MOD


ans = 1
for num in cnt.values():
    ans = (ans * comb(N + num - 1, num)) % MOD
print(ans)

Submission status: Runtime Error

Solution code:
# encoding: utf-8
import math
N, M = map(int, input().split())

def distribute(pos, full, tmp):
    return memo[tmp][pos]

# define search range
p_max = int(M / 2) # M is prime if M has a factor p (> p_max)
ip_up = int(math.log2(p_max))

#### O(MlogM) below (if M has a very large prime factor)
M_tmp = M
ips = []
for p in range(2, p_max + 1):
    if M_tmp % p > 0: continue
    # how many times M_tmp can be divided
    p_tmp = p
    for i_p in range(ip_up + 1):
        if M_tmp % p_tmp > 0: break
        p_tmp = p_tmp * p
    # calculate later
    ips.append(i_p)
    # next
    M_tmp = M_tmp // (p_tmp // p)
    if M_tmp == 1: break
#### O(Mlog M) above

#### O(N) below
# create memo
## init
if len(ips) > 0: ip_max = max(ips)
else: ip_max = 0
memo = [[None] * N for i in range(ip_max + 1)] # max ip
for j in range(N): memo[0][j] = 1
for i in range(1, ip_max + 1): memo[i][N - 1] = 1
## fill
for i in range(1, ip_max + 1):
    sum_tmp = 0
    vals = list(memo[i - 1])[::-1]
    p_memo = memo[i]
    for j, val in enumerate(vals):
        sum_tmp += val
        p_memo[N - 1 - j] = sum_tmp
#### O(N) above
        
# calculate ans
ans = 1
for i_p in ips: ans = (ans * distribute(0, i_p, i_p)) % (10 ** 9 + 7)

if ip_max == 0: print(N)
else: print(ans)

Submission status: Runtime Error

Solution code:
# encoding: utf-8
import math
N, M = map(int, input().split())

def distribute(pos, full, tmp):
    return memo[tmp][pos]

# define search range
p_max = int(M / 2) # M is prime if M has a factor p (> p_max)
ip_up = int(math.log2(p_max))

#### O(MlogM) below (if M has a very large prime factor)
M_tmp = M
ips = []
for p in range(2, p_max + 1):
    if M_tmp % p > 0: continue
    # how many times M_tmp can be divided
    p_tmp = p
    for i_p in range(ip_up + 1):
        if M_tmp % p_tmp > 0: break
        p_tmp = p_tmp * p
    # calculate later
    ips.append(i_p)
    # next
    M_tmp = M_tmp // (p_tmp // p)
    if M_tmp == 1: break
#### O(Mlog M) above

#### O(N) below
# create memo
## init
if len(ips) > 0: ip_max = max(ips)
else: ip_max = 0
memo = [[None] * N for i in range(ip_max + 1)] # max ip
for j in range(N): memo[0][j] = 1
for i in range(1, ip_max + 1): memo[i][N - 1] = 1
## fill
for i in range(1, ip_max + 1):
    sum_tmp = 0
    vals = list(memo[i - 1])[::-1]
    p_memo = memo[i]
    for j, val in enumerate(vals):
        sum_tmp += val
        p_memo[N - 1 - j] = sum_tmp
#### O(N) above
        
# calculate ans
ans = 1
for i_p in ips: ans = (ans * distribute(0, i_p, i_p)) % (10 ** 9 + 7)

if ip_max = 0: print(N)
else: print(ans)

Submission status: Runtime Error

Solution code:
# encoding: utf-8
import math
N, M = map(int, input().split())

def distribute(pos, full, tmp):
    return memo[tmp][pos]

# define search range
p_max = int(M / 2) # M is prime if M has a factor p (> p_max)
ip_up = int(math.log2(p_max))

#### O(MlogM) below (if M has a very large prime factor)
M_tmp = M
ips = []
for p in range(2, p_max + 1):
    if M_tmp % p > 0: continue
    # how many times M_tmp can be divided
    p_tmp = p
    for i_p in range(ip_up + 1):
        if M_tmp % p_tmp > 0: break
        p_tmp = p_tmp * p
    # calculate later
    ips.append(i_p)
    # next
    M_tmp = M_tmp // (p_tmp // p)
    if M_tmp == 1: break
#### O(Mlog M) above

#### O(N) below
# create memo
## init
if len(ips) > 0: ip_max = max(ips)
else: ip_max = 0
memo = [[None] * N for i in range(ip_max + 1)] # max ip
for j in range(N): memo[0][j] = 1
for i in range(1, ip_max + 1): memo[i][N - 1] = 1
## fill
for i in range(1, ip_max + 1):
    sum_tmp = 0
    vals = list(memo[i - 1])[::-1]
    p_memo = memo[i]
    for j, val in enumerate(vals):
        sum_tmp += val
        p_memo[N - 1 - j] = sum_tmp
#### O(N) above
        
# calculate ans
ans = 1
for i_p in ips: ans = (ans * distribute(0, i_p, i_p)) % (10 ** 9 + 7)
    
print(ans)

Submission status: Runtime Error

Solution code:
# encoding: utf-8
import math
N, M = map(int, input().split())

def distribute(pos, full, tmp):
    return memo[tmp][pos]

# define search range
p_max = int(M / 2) # M is prime if M has a factor p (> p_max)
ip_up = int(math.log2(p_max))

#### O(MlogM) below (if M has a very large prime factor)
M_tmp = M
ips = []
for p in filter(lambda x: M % x == 0, range(2, p_max + 1)):
    # how many times M_tmp can be divided
    p_tmp = p
    for i_p in range(ip_up + 1):
        if M_tmp % p_tmp > 0: break
        p_tmp = p_tmp * p
    # escape if M_tmp cannot be divided
    if i_p < 1: continue
    # calculate later
    ips.append(i_p)
    # next
    M_tmp = M_tmp // (p_tmp // p)
    if M_tmp == 1: break
#### O(Mlog M) above

#### O(N) below
# create memo
## init
if len(ips) > 0: ip_max = max(ips)
else: ip_max = 0
memo = [[None] * N for i in range(ip_max + 1)] # max ip
for j in range(N): memo[0][j] = 1
for i in range(1, ip_max + 1): memo[i][N - 1] = 1
## fill
for i in range(1, ip_max + 1):
    sum_tmp = 0
    vals = list(memo[i - 1])[::-1]
    p_memo = memo[i]
    for j, val in enumerate(vals):
        sum_tmp += val
        p_memo[N - 1 - j] = sum_tmp
#### O(N) above
        
# calculate ans
ans = 1
for i_p in ips: ans = (ans * distribute(0, i_p, i_p)) % (10 ** 9 + 7)
    
print(ans)

Submission status: Runtime Error

Solution code:
# encoding: utf-8
import math
N, M = map(int, input().split())

def distribute(pos, full, tmp):
    return memo[tmp][pos]

# define search range
p_max = int(M / 2) # M is prime if M has a factor p (> p_max)
ip_up = int(math.log2(p_max))

#### O(MlogM) below (if M has a very large prime factor)
M_tmp = M
ips = []
psuedo_primes = [max((2, 2 * i + 1)) for i in range(p_max // 2)]
for p in psuedo_primes:
    # how many times M_tmp can be divided
    p_tmp = p
    for i_p in range(ip_up + 1):
        if M_tmp % p_tmp > 0: break
        p_tmp = p_tmp * p
    # escape if M_tmp cannot be divided
    if i_p < 1: continue
    # calculate later
    ips.append(i_p)
    # next
    M_tmp = M_tmp // (p_tmp // p)
    if M_tmp == 1: break
#### O(Mlog M) above

#### O(N) below
# create memo
## init
if len(ips) > 0: ip_max = max(ips)
else: ip_max = 0
memo = [[None] * N for i in range(ip_max + 1)] # max ip
for j in range(N): memo[0][j] = 1
for i in range(1, ip_max + 1): memo[i][N - 1] = 1
## fill
for i in range(1, ip_max + 1):
    sum_tmp = 0
    vals = list(memo[i - 1])[::-1]
    p_memo = memo[i]
    for j, val in enumerate(vals):
        sum_tmp += val
        p_memo[N - 1 - j] = sum_tmp
#### O(N) above
        
# calculate ans
ans = 1
for i_p in ips: ans = (ans * distribute(0, i_p, i_p)) % (10 ** 9 + 7) # oh...
    
print(ans)