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:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import Counter

def factorize(n: int):
    d = Counter()
    m= 2
    
    while m*m <= n:
        while n%m == 0:
            n //= m
            d[m] += 1
            
        m += 1
        
    if n > 1:
        d[n] += 1
        
    return d

# nの逆元のリスト
def inv_mod(n:int, mod:int) -> list:
    inv = [0,1]
    for i in range(2,n+1):
        inv.append(mod - ((mod//i)*inv[mod%i]) % mod)
    return inv
       
# nの階乗のリスト
def fact(n:int, mod:int) -> list:
    fac = [1,1]
    res = 1
    for i in range(2,n+1):
        res = res*i%mod
        fac.append(res)
    return fac

# nの階乗の逆元のリスト
def fact_inv(n:int, inv:list, mod:int) -> list:
    facInv = [1,1]
    for i in range(2,n+1):
        facInv.append(facInv[i-1]*inv[i] % mod)
    return facInv
        
# 二項係数
def nCr(n:int, r:int, mod:int, fac:list, facInv:list) -> int:
    if not (0<=r and r<=n):
        return 0
    
    return ((fac[n]*facInv[r]) % mod) * facInv[n-r] % mod

# 重複組み合わせ
def nHr(n:int, r:int, mod:int, fac:list, facInv:list) -> int:
    if r<0 or n<0:
        return 0
    
    else:
        return nCr(n+r-1,r,mod,fac,facInv)

n,m = li()
MOD = 10**9+7

inv = inv_mod(2*n, MOD)
fac = fact(2*n, MOD)
facinv = fact_inv(2*n,inv,MOD)

md = factorize(m)

ans = 1
for k,v in md.items():
    ans *= nHr(n,v,MOD,fac,facinv)
    ans %= MOD
    
print(ans)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())

from collections import Counter
def factorize(n):
    d = Counter()
    m = 2
    while m*m <= n:
        while n%m == 0:
            n //= m
            d[m] += 1
        m += 1
    if n > 1:
        d[n] += 1
    return d

MOD = 10**9+7

fac = [1,1] + [0]*(N*2)
finv = [1,1] + [0]*(N*2)
inv = [0,1] + [0]*(N*2)
for i in range(2,(N*2)+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

def ncr(n,r):
    if n < r: return 0
    if n < 0 or r < 0: return 0
    return fac[n] * (finv[r] * finv[n-r] % MOD) % MOD
def nhr(n,r):
    return ncr(n+r-1, r)


factors = factorize(M)
ans = 1
for v in factors.values():
    ans *= nhr(N,v)
    ans %= MOD
print(ans)

Submission status: Runtime Error

Solution code:
import math


def factorization(n):
    R = int(n)
    s = 0
    L = []
    div = 2
    while s == 0:
        for i in range(div, R + 1):
            if n % i == 0:
                n = n / i
                div = i
                if n == 1:
                    s = 1
                L.append(i)
                break
    return L


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


def cmb(n, r, mod):
    if r < 0 or r > n:
        return 0
    r = min(r, n - r)
    return g1[n] * g2[r] * g2[n - r] % mod


mod = 10 ** 9 + 7  # 出力の制限
N = 10 ** 5 + 10
g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  # 逆元テーブル
inverse = [0, 1]  # 逆元テーブル計算用テーブル

for i in range(2, N + 1):
    g1.append((g1[-1] * i) % mod)
    inverse.append((-inverse[mod % i] * (mod // i)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)

n, m = [int(i) for i in input().split()]
# n, m = 3, 12
div = factorization(m)
divList = []
prevDiv = 0
for i in range(len(div)):
    if div[i] == prevDiv:
        divList[-1] += 1
    else:
        divList.append(1)
        prevDiv = div[i]
# print(divList)

count = 1
for i in range(len(divList)):
    # print("{}:{}".format(divList[i]+n-1, n-1))
    # print(combinations_count(divList[i]+n-1, n-1))
    count *= cmb(divList[i] + n - 1, divList[i], mod)
    # count *= combinations_count(divList[i] + n - 1, divList[i])
print(count % (10 ** 9 + 7))

Submission status: Runtime Error

Solution code:
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def combinations_with_replacement_count(n, r):
    return combinations_count(n + r - 1, r)
nm = list(map(int, input().split()))
n = nm[0]
m = nm[1]
fact = list()
i = 2
while m != 1:
    if m % i == 0:
        m = m // i
        fact.append(i)
    else:
        i += 1
j = 2
ans = 1
while j <= fact[-1]:
    ans = ans * combinations_with_replacement_count(n, fact.count(j))
    j += 1
print(ans % (10 ** 9 + 7))

Submission status: Runtime Error

Solution code:
import math


def combinations_with_replacement_count(n, r):
    return math.factorial(n + r - 1) // (math.factorial(n - 1) * math.factorial(r))


nm = list(map(int, input().split()))
n = nm[0]
m = nm[1]
fact = list()
i = 2
while m != 1:
    while m % i == 0:
        m = m // i
        fact.append(i)
    i += 1
j = 2
ans = 1
fact_c = list()
while j <= fact[-1]:
    fact_c.append(fact.count(j))
    j += 1
for k in fact_c:
    ans = ans * combinations_with_replacement_count(n, k)
print(ans % (10 ** 9 + 7))

Submission status: Runtime Error

Solution code:
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def combinations_with_replacement_count(n, r):
    return combinations_count(n + r - 1, r)
nm = list(map(int, input().split()))
n = nm[0]
m = nm[1]
fact = list()
i = 2
while m != 1:
    if m % i == 0:
        m = m // i
        fact.append(i)
    else:
        i += 1
j = 2
ans = 1
while j <= fact[-1]:
    ans = ans * combinations_with_replacement_count(n, fact.count(j))
    j += 1
print(ans % (10 ** 9 + 7))

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
soinsuubunkai={}
tmp=1
i=2
_M=M
while(i <=M and i**2 <=_M):
    if(M%i==0):
        if(i in soinsuubunkai):
            soinsuubunkai[i]+=1
        else:
            soinsuubunkai[i]=1
        M//=i
    else:
        i+=1

tmp=1
for k in list(soinsuubunkai.values()):
    tmp*=com(k+N-1,k)
    tmp%=10**9+7
print(tmp)

Submission status: Runtime Error

Solution code:
# import sys
from math import factorial
from functools import reduce


def mmul(a, b, mod):
    return (a % mod) * (b % mod) % mod


def mfact(a, mod):
    fact = 1
    for m in range(2, a + 1):
        fact *= m % mod
        fact %= mod
    return fact


def mpow(a, b, mod):
    if b == 0:
        return 1
    if b == 1:
        return a % mod
    if b % 2 == 0:
        return mpow(a, b / 2, mod) ** 2 % mod
    return mpow(a, b // 2, mod) ** 2 * a % mod


def mdiv(a, b, mod):
    return mmul(a, mpow(b, mod - 2, mod), mod)


# (n+a)Ca = (n+a)! / n!a! mod mod for n >> a
def mnpaca(n, a, mod):
    res = 1
    for num in range(n + 1, n + a + 1):
        res *= num % mod
        res %= mod
    return mdiv(res, factorial(a), mod)

mod = 1000000007
N, M = [int(s) for s in input().split()]

prime_counts = []
i = 2
while i * i <= M:
    count = 0
    while M % i == 0:
        M /= i
        count += 1
    if count:
        prime_counts.append(count)
    i += 1
if M > 1:
    prime_counts.append(1)

res = reduce(lambda x, y: x * y, [mnpaca(N - 1, c, mod) for c in prime_counts])

print(res % mod)

Submission status: Runtime Error

Solution code:
import math
n,m = list(map(int,input().split()))

#素数列挙
m_sqr = math.floor(math.sqrt(m))
tf = [True]*(m+1)
for i in range(2,math.floor(math.sqrt(m)+1)):
  if tf[i] == True:
    for j in range(i+1,m+1):
      if j % i == 0:
        tf[j] = False

prim = []
for i in range(2,m+1):
  if tf[i]:
    prim.append(i)

divm = m
ans = 1
for i in prim:
  cnt = 0
  if m%i == 0:
    while divm%i == 0:
      cnt += 1
      divm /= i
    
    ans *= math.factorial(cnt+n-1) / (math.factorial(n -1) * math.factorial(cnt))

print(int(ans) % 1000000007)

Submission status: Runtime Error

Solution code:
def factoring2(max_input):
    pf = []
    n1 = max_input
    data = [1] * (max_input+1)
    m = 2
    n = 0
    while n1 % m == 0:
        n1 //= m
        pf.append(m)
    data[0] = 0
    data[1] = 0
    while 1:
        # print(m)
        if data[m] == 1:
            i = 2 * m
            while i <= max_input:
                data[i] = 0
                i += m
            while n1 % m == 0:
                n1 //= m
                pf.append(m)
            n += 1
            m += 1
        else:
            m += 1
        if n1 == 1:
            return pf

from collections import Counter
from itertools import combinations
n, m = map(int, input().split())
dic = Counter(factoring2(m))
fact_list = list(dic.values())

sol = 1
for val in fact_list:
    sol *= len(list(combinations(range(val+n-1), val)))

print(sol)

Submission status: Runtime Error

Solution code:
def factoring2(max_input):
    pf = []
    n1 = max_input
    data = [1] * (max_input+1)
    m = 2
    n = 0
    while n1 % m == 0:
        n1 //= m
        pf.append(m)
    data[0] = 0
    data[1] = 0
    while 1:
        # print(m)
        if data[m] == 1:
            i = 2 * m
            while i <= max_input:
                data[i] = 0
                i += m
            while n1 % m == 0:
                n1 //= m
                pf.append(m)
            n += 1
            m += 1
        else:
            m += 1
        if n1 == 1:
            return pf

from factoring import factoring
from collections import OrderedDict
from itertools import combinations

fact_list = list(OrderedDict(factoring(m)).values())

sol = 1
for val in fact_list:
    sol *= len(list(combinations(range(val+n-1), val)))

print(sol)

Submission status: Runtime Error

Solution code:
from collections import Counter as c
from scipy.misc import comb
from functools import reduce

def f(n):
  d,i=c(),2
  while i*i<=n:
    while n%i==0:
      n//=i
      d[i]+=1
    i+=1
  if n>1:d[n]+=1
  return d.values()

n,m=map(int,input().split())
mod=10**9+7
print(reduce(lambda x,y:((x%mod)*(y%mod))%mod,map(lambda x:comb(x+n-1,x,exact=True)%mod,f(m)))%mod)

Submission status: Runtime Error

Solution code:
from collections import Counter as c
from scipy.misc import comb
from functools import reduce

def f(n):
  d,i=c(),2
  while i*i<=n:
    while n%i==0:
      n//=i
      d[i]+=1
    i+=1
  if n>1:d[n]+=1
  return d.values()

n,m=map(int,input().split())
mod=10**9+7
print(reduce(lambda x,y:x*y%mod,map(lambda x:comb(x+n-1,x,exact=True)%mod,f(m)))%mod)

Submission status: Runtime Error

Solution code:
from collections import Counter as c
from scipy.misc import comb
from functools import reduce

def f(n):
  d,i=c(),2
  while i*i<=n:
    while n%i==0:
      n//=i
      d[i]+=1
    i+=1
  if n>1:d[n]+=1
  return d.values()

n,m=map(int,input().split())
mod=10**9+7
print(reduce(lambda x,y:x*y%mod,map(lambda x:comb(x+n-1,x,exact=True),f(m)))%mod)

Submission status: Runtime Error

Solution code:
from collections import Counter as c
from math import factorial as fac
from functools import reduce

def f(n):
  d=c()
  for i in range(2,1+int(n**0.5)):
    while n%i==0:
      d[i]+=1
      n/=i
  return d.values()

def comb(n,r):
  return fac(n)//fac(r)//fac(n-r)%mod

n,m=map(int,input().split())
mod=10**9+7
g=lambda x:comb(x+n-1,x)
h=lambda x,y:x*y%mod
print(reduce(h,map(g,f(m)))%mod)

Submission status: Runtime Error

Solution code:
N, M=map(int,input().split())
dic={}
def f(num):
    if not num in dic:
        lis=[]
        for i in range(1,int(num**0.5)+1):
            if num%i==0:
                lis.append(i)
                if i**2!=num:
                    lis.append(num//i)
        lis.sort()
        dic[num]=lis
    return dic[num]

res=0
def c(m,n):
    if n>0:
        for i in f(m):
            j=m//i
            c(j,n-1)
    else:
        global res
        res+=len(f(m))

c(M,n=N-2)
print(res)

Submission status: Runtime Error

Solution code:
N, M=map(int,input().split())
def f(num):
    lis=[]
    for i in range(1,int(num**0.5)+1):
        if num%i==0:
            lis.append(i)
            if i**2!=num:
                lis.append(num//i)
    lis.sort()
    return lis

res=0
def c(m,n):
    if n>0:
        print(n,m,f(m))
        for i in f(m):
            j=m//i
            c(j,n-1)
    else:
        global res
        res+=len(f(m))

c(M,n=N-2)
print(res)

Submission status: Runtime Error

Solution code:
from collections import Counter


def main():
    """
    1 <= N <= 10^5
    1 <= M <= 10^9

    正整数 N, M
    a1 * a2 * ... * aN = M となる長さNの数列a
    何通りあるか
    数列A1-ai != 数列A2-ai
    """
    N, M = map(int, input().split())

    ans = editorial(N, M)
    print(ans)


def factorize(N):
    """素因数分解

    TODO: もっと速い方法
    素因数がある場合は範囲をsqrtで狭められるが、ない場合愚直に探してしまう
    N以下の素数を見つけて、それだけで対応すれば速いはず
    """
    import math
    factors = []
    while True:
        if N % 2 == 0:
            factors.append(2)
            N //= 2
        else:
            break
    m = int(math.sqrt(N))
    i = 3
    while i <= m:
        add = False
        while True:
            if N % i == 0:
                factors.append(i)
                N //= i
                add = True
            else:
                break
        if add:
            m = int(math.sqrt(N))
        i += 2
    if N > 1:
        factors.append(N)
    return factors


def f(N, M):
    """
    M を素因数分解すると約数とそれらの個数がわかる
    それらの組合せを制約を満たすようにする
    1 * M, M * 1 をわすれないこと:
        1 * 1 * 1 * M もOK

    3 12
        1,1,12: 3P3 / 2!
        2,2,3:  3P3 / 2!
        3,4,1:  3P3
        6,2,1:  3P3

    http://sucrose.hatenablog.com/entry/2014/10/10/235805
    """
    ans = 0
    m = 10 ** 9 + 7
    factors = factorize(M)
    c = Counter(factors)
    print(c)
    return ans


def editorial(N, M):
    """
    https://mathtrain.jp/tyohukuc

    3 12 の例で示せているのに、重複組合せという言葉が頭に浮かばなかった

    解説動画より
    modの世界における逆元?
        重複組合せ
            フェルマーの小定理
            階乗と階乗逆元
        拡張ユークリッド互除法
            今回は出番なし
    """
    def create_tables(N, MOD):
        """
        http://drken1215.hatenablog.com/entry/2018/06/08/210000
        """
        fact_mod = [0] * (N + 1)
        simod = [0] * (N + 1)
        fact_inv_mod = [0] * (N + 1)

        fact_mod[0] = fact_mod[1] = 1
        simod[0] = simod[1] = 1
        fact_inv_mod[0] = fact_inv_mod[1] = 1

        for i in range(2, N + 1):
            fact_mod[i] = (fact_mod[i - 1] * i) % MOD
            simod[i] = MOD - simod[MOD % i] * (MOD // i) % MOD
            fact_inv_mod[i] = (fact_inv_mod[i - 1] * simod[i]) % MOD
            # inv 配列が確実に不要な場面 とは？ (ここでのsimod)
            # inv[n] を逆元計算によって計算しておく
            # finv[i-1] = finv[i] * i % MOD によって finv 配列を後ろから計算していく

        return fact_mod, fact_inv_mod

    def create_fact_mod(N, MOD):
        fact_mod = [0] * (N + 1)
        fact_mod[0] = 1
        fact_mod[1] = 1

        # 階乗のテーブル作成, 累積積によって計算量を落としている
        for i in range(2, N + 1):
            fact_mod[i] = (fact_mod[i - 1] * i) % MOD

        return fact_mod

    def create_seq_inv_mod(N, MOD):
        simod = [0] * (N + 1)
        simod[0] = 1  # 0のままでもよい?
        simod[1] = 1

        # 階乗逆元のテーブル用に作成
        for i in range(2, N + 1):
            simod[i] = (MOD - MOD // i) * simod[MOD % i] % MOD
            # 下記との違いはなにか？
            # simod[i] = MOD - simod[MOD % i] * (MOD // i) % MOD

        return simod

    def create_fact_inv_mod(N, MOD, simod):
        fact_inv_mod = [0] * (N + 1)
        fact_inv_mod[0] = 1
        fact_inv_mod[1] = 1

        # 階乗逆元のテーブル作成
        for i in range(2, N + 1):
            fact_inv_mod[i] = (fact_inv_mod[i - 1] * simod[i]) % MOD

        return fact_inv_mod

    def comb_mod(N, R, fact_mod, fact_inv_mod, MOD):
        """
        組合せ nCr: n! / ((n-r)! * r!)
        上記のmodを逆元を使って表現

        f[n] * f[r] % MOD * f[n-r] % MOD 
        これのために事前にテーブルを作っていた
        """
        return fact_mod[N] * fact_inv_mod[N - R] * fact_inv_mod[R] % MOD

    ans = 1
    m = 10 ** 9 + 7
    factors = factorize(M)
    c = Counter(factors)

    # ref:
    # https://beta.atcoder.jp/contests/abc110/submissions/3253308
    # http://betrue12.hateblo.jp/entry/2018/09/24/020414
    fact_mod = create_fact_mod(N + 10, m)
    simod = create_seq_inv_mod(N + 10, m)
    fact_inv_mod = create_fact_inv_mod(N + 10, m, simod)

    # 重複組合せ: n! / (a! * (b - a)!)
    # 重複組合せ を 各素因数における組合せ結果の掛け合わせで表現
    for i in c.values():
        ans *= comb_mod(N - 1 + i, i, fact_mod, fact_inv_mod, m)
        ans %= m

    return ans


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import math
def nCr(n,r):
    return math.factorial(n) / math.factorial(r) / math.factorial(n-r)
def nHr(n,r):
    return nCr(n+r-1, r-1)
def prime(n): # nまでの素数を列挙
    import math
    num_list = [i + 1 for i in range(2,n,2)]
    list_prime = [2]
    limit = math.sqrt(n)
    if n == 2:
        return list_prime
    else:
        while True:
            p = num_list[0]
            if p >= limit:
                return list_prime + num_list
            list_prime.append(p)
            num_list = [num for num in num_list if num % p != 0]

def primeFactorization(n):
    import math
    list_prime = prime(int(math.sqrt(n)))
    i = 0
    dict_pF = {}
    dict_primeFactorization = {}
    for pri in list_prime:
        dict_pF[pri] = 0
    while True:
        if n == 1:
            for key, value in dict_pF.items():
                if value != 0:
                    dict_primeFactorization[key] = value
            return dict_primeFactorization
        elif i >= len(list_prime):
            dict_pF[n] = 1
            for key, value in dict_pF.items():
                if value != 0:
                    dict_primeFactorization[key] = value
            return dict_primeFactorization
        p = list_prime[i]
        if n % p == 0:
            n //= p
            dict_pF[p] += 1
            continue
        else:
            i += 1

ans = 1
n,m = map(int, input().split())
for factor,degree in primeFactorization(m).items():
    ans *= nHr(degree,n)

print(int(ans) % (10**9+7))

Submission status: Runtime Error

Solution code:
import math
# import time


def get_primes(n):
    primes = []
    checks = [True for _ in range(int(math.sqrt(n)))]
    checks[0] = checks[1] = False
    for i in range(2, len(checks)):
        if checks[i]:
            primes.append(i)
            tmp = 0
            while i + tmp * i < len(checks):
                checks[i + tmp * i] = False
                tmp += 1
    return primes


def combination(a, b):
    i = 1
    for _i in range(a - b+1, a + 1):
        i *= _i
    return i // math.factorial(b)


n, m = map(int, input().split())
# start = time.time()
primes = get_primes(m)
elems = []
m_copy = m
divides = dict()
for _p in primes:
    while m_copy % _p == 0:
        m_copy = m_copy // _p
        if str(_p) in divides.keys():
            divides[str(_p)] += 1
        else:
            divides[str(_p)] = 1
if m_copy > 1:
    divides[str(m_copy)] = 1

# print(time.time() - start)
ans = 1
for i in divides.values():
    ans *= combination(i + n - 1, i)
print(ans % (1000000007))
# print(time.time() - start)

Submission status: Runtime Error

Solution code:
import math


# """
def get_primes(n):
    primes = []
    checks = [True for _ in range(int(math.sqrt(n)))]
    checks[0] = checks[1] = False
    for i in range(2, len(checks)):
        if checks[i]:
            primes.append(i)
            tmp = 0
            while i + tmp * i < len(checks):
                checks[i + tmp * i] = False
                tmp += 1
    return primes


def combination(a, b):
    return math.factorial(a) // math.factorial(a - b) // math.factorial(b)


n, m = map(int, input().split())
primes = get_primes(m)
elems = []
m_copy = m
divides = dict()
for _p in primes:
    while m_copy % _p == 0:
        m_copy = m_copy // _p
        if str(_p) in divides.keys():
            divides[str(_p)] += 1
        else:
            divides[str(_p)] = 1
if m_copy > 1:
    divides[str(m_copy)] = 1
ans = 1
for i in divides.values():
    ans *= combination(i + n - 1, i)
print(ans % (1000000007))

Submission status: Runtime Error

Solution code:
import time
import collections
import scipy.special

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

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

factors = collections.Counter(prime_decomposition(M))
t_elps = time.time()
#print(f"{t_elps - t_strt} [sec]")
num_pattern = 1;

for exponent in factors.values():
    tmp_num_pattern = scipy.special.comb(exponent + N -1, N-1, exact = True) 
    num_pattern = num_pattern * int(tmp_num_pattern)
    
#print(num_pattern%(10**9+7))

t_elps = time.time()
print(f"{t_elps - t_strt} [sec]")

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, math
class Combination:
    def __init__(self, fact=math.factorial, div=operator.itruediv):
        self.fact = fact
        self.div = div
    def comb(self, n, m):
        if n < m: return 0
        if m == 0 or n == m: return 1
        return self.div(
                self.fact(n),
                self.fact(n - m) * self.fact(m)
            )

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

class CachedFactorial:
    def __init__(self, n, mod):
        self.mod = mod
        self.fact_cache = list(
                itertools.accumulate(
                        itertools.chain(
                                [1],
                                range(1, n+1)
                        ),
                        lambda a,x: (a * x) % mod
                )
        )
    def factorial(self, n):
        return self.fact_cache[n]

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

        self.n = n
        self.fact = CachedFactorial(n, mod)
        super().__init__(
             self.fact.factorial,
             lambda x, y: (x * self.gfp.inv(y)) % self.mod
        )

cc = CachedComb(N + max(x[1] for x in ps), mod)
ans = 1
for p, c in ps:
    cmb = cc.comb(N - 1 + c, c)
    ans = ans * cmb % mod
print(ans)

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
class GFp:
    def __init__(self, p):
        self.p = p
    def inv(self, v):
        return pow(v, self.p - 2, self.p)

class CachedFactorial:
    def __init__(self, n, mod):
        self.mod = mod
        self.fact_cache = list(
                itertools.accumulate(
                        itertools.chain(
                                [1],
                                range(1, n+1)
                        ),
                        lambda a,x: (a * x) % mod
                )
        )
        
    def factorial(self, n):
        return self.fact_cache[n]
        

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

        self.n = n
        self.fact = CachedFactorial(n, mod)
        
    def comb(self, n, m):
        if n < m: return 0
        if m == 0 or n == m: return 1
        return self.fact.factorial(n) * self.gfp.inv(
                self.fact.factorial(n - m) * self.fact.factorial(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:
#!/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=500000, 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):
    if not xs:
        return 1
    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()