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:
N, M = map(int, input().split())
mod = 10 ** 9 + 7
m = 0


def factorization(n):
    if n == 1:
        return []
    arr = []
    temp = n
    global m
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append((i, cnt))
            m = max(m, cnt)

    if temp!=1:
        arr.append((temp, 1))

    if arr==[]:
        arr.append((n, 1))

    return arr


fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]


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


for i in range(2, N + m + 10):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)


A = factorization(M)
ans = 1

for (key, value) in A:
    ans *= cmb(value + N - 1, value)
    ans %= mod

print(ans)

Submission status: Runtime Error

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


def factorization(n):
    if n == 1:
        return []
    arr = []
    temp = n
    global m
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append((i, cnt))
            m = max(m, cnt)

    if temp!=1:
        arr.append((temp, 1))

    if arr==[]:
        arr.append((n, 1))

    return arr


fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]


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


for i in range(2, N + m + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)


A = factorization(M)
ans = 1

for (key, value) in A:
    ans *= cmb(value + N - 1, value)
    ans %= mod

print(ans)

Submission status: Runtime Error

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


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append((i, cnt))

    if temp!=1:
        arr.append((temp, 1))

    if arr==[]:
        arr.append((n, 1))

    return arr


fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]


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


for i in range(2, 2 * N + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)


A = factorization(M)
ans = 1

for (key, value) in A:
    ans *= cmb(value + N - 1, value)
    ans %= mod

print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter
from math import factorial
N,M = map(int,input().split())

# 因数分解
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

# 重複組み合わせ
# フェルマーの小定理nHk≡(n+k−1)!⋅(k!)M−2⋅((n−1)!)M−2(modM)
def comb(n,k,p):
    """power_funcを用いて(nCk) mod p を求める"""
    if n<=0 or k<0 or n<k: return 0
    if k==0　or n==1: return 1
    a=factorial(n+k-1) %p
    b=factorial(k) %p
    c=factorial(n-1) %p
    return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p

def power_func(a,b,p):
    """a^b mod p を求める"""
    if b==0: return 1
    if b%2==0:
        d=power_func(a,b//2,p)
        return d*d %p
    if b%2==1:
        return (a*power_func(a,b-1,p ))%p

a = prime_factorize(M)
c = Counter(a)
l = []
ans = 1
for i in c.values():
    # それぞれの余りがわかっている時、その積の余りを求める時は以下
    ans *= comb(N,i,10**9+7)
    ans %= 10**9+7

print(ans)

Submission status: Runtime Error

Solution code:
# D - Factorization

N, M = map(int, input().split())
MOD = 10**9 + 7

def prime_factorization(n):
    prime_factors = []
    if n < 2:
        return 0
    for i in range(2, int(pow(n, 0.5)+1)):
        if n%i==0:
            ex = 0
            while n%i==0:
                ex += 1
                n //= i
            prime_factors.append((i, ex))
    if n!=1:
        prime_factors.append((n,1))
    return prime_factors

fac = [1, 1]
inv = [0, 1]
finv = [1, 1]

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

def comb_mod(n, r, m):
    if (n<0 or r<0 or n<r): return 0
    r = min(r, n-r)
    return fac[n] * finv[n-r] * finv[r] % m

primes = prime_factorization(M)
ans = 1
for p, ex in primes:
    ans = (ans * comb_mod(ex+N-1, N-1, MOD)) % MOD

print(ans)

Submission status: Runtime Error

Solution code:
# D - Factorization

N, M = map(int, input().split())
MOD = 10**9 + 7

# M を素因数分解する 12 -> 2^2 * 3^1
# 2^2 と 3^1 の組み合わせをそれぞれ計算する。
# 2^2 は べき数を配分する組み合わせ。
# N=3の時、
# 2^2, 2^0, 2^0 -> 4, 1, 1
# 2^1, 2^1, 2^0 -> 2, 2, 1
# この組み合わせは べき数をxとした時、
# N-1個の区切り場所を追加したと仮定して、
# (x+N-1)C(N-1) 

def prime_factorization(n):
    prime_factors = []
    if n < 2:
        return 0
    for i in range(2, int(pow(n, 0.5)+1)):
        if n%i==0:
            ex = 0
            while n%i==0:
                ex += 1
                n //= i
            prime_factors.append((i, ex))
    # 割り切れなかった残りのnが1でない(素数)場合、リストに加える
    if n!=1:
        prime_factors.append((n,1))
    return prime_factors

fac = [1, 1]
inv = [0, 1]
finv = [1, 1]

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

def comb_mod(n, r, m):
    if (n<0 or r<0 or n<r): return 0
    r = min(r, n-r)
    return fac[n] * finv[n-r] * finv[r] % m

primes = prime_factorization(M)
ans = 1
for p, ex in primes:
    ans = (ans * comb_mod(ex+N-1, N-1, MOD)) % MOD

print(ans)

Submission status: Runtime Error

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,M = LI()

    d = {}
    m = M
    for i in range(2,int(math.sqrt(M))+1):
        while m % i == 0:
            if i in d:
                d[i] += 1
            else:
                d[i] = 1
            m //= i
    if m > 1:
        d[m] = 1

    a = [0]
    b = [0]
    c = 1
    for i in range(1,N+(int(math.log(N,2))+2)**2 +1):
        c = (c * i) % MOD
        a.append(c)
        b.append(pow(c,MOD-2,MOD))

    ans = 1
    for v in d.values():
        ans = (ans * a[N+v-1] * b[v]* b[N-1]) % MOD
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N,M = LI()

    d = {}
    m = M
    for i in range(2,int(math.sqrt(M))+1):
        while m % i == 0:
            if i in d:
                d[i] += 1
            else:
                d[i] = 1
            m //= i
    if m > 1:
        d[m] = 1

    a = [0]
    b = [0]
    c = 1
    for i in range(1,N+(int(math.log(N,2))+1)**2 +1):
        c = (c * i) % MOD
        a.append(c)
        b.append(pow(c,MOD-2,MOD))

    ans = 1
    for v in d.values():
        ans = (ans * a[N+v-1] * b[v]* b[N-1]) % MOD
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N,M = LI()

    d = {}
    m = M
    for i in range(2,int(math.sqrt(M))+1):
        while m % i == 0:
            if i in d:
                d[i] += 1
            else:
                d[i] = 1
            m //= i
    if m > 1:
        d[m] = 1

    a = [0]
    b = [0]
    c = 1
    for i in range(1,N+int(math.log(N,2))**2+1):
        c = (c * i) % MOD
        a.append(c)
        b.append(pow(c,MOD-2,MOD))

    ans = 1
    for v in d.values():
        ans = (ans * a[N+v-1] * b[v]* b[N-1]) % MOD
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import collections as col
import numpy as np
import math as ma
import scipy.misc as spm #miscellaneous

MOD = 10**9 + 7
def inv(a): return pow(a, MOD-2, MOD)
def comb(n,r):
    ans = ma.factorial(n)%MOD * inv(ma.factorial(r)) * inv(ma.factorial(n-r))
    return ans%MOD

def prime(n):
    ans = []
    for i in range(2, int(n**0.5)+1):
        while not n%i: n //= i; ans.append(i)
    if n != 1: ans.append(n)
    return ans

n,m = map(int,input().split())
cnt = col.Counter(prime(m))

ans = 1
for key,val in cnt.items():
    #ans *= comb(val + n-1, n-1)
    ans *= comb(val + n-1, n-1, MOD)
    ans %= MOD
print(ans)

Submission status: Runtime Error

Solution code:
import collections as col
import itertools as ite
import numpy as np
import math as ma
from scipy.special import comb

MOD = 10**9 + 7
def inv(a): return pow(a, MOD-2, MOD)
def cmb(n,r):
    ans = ma.factorial(n)%MOD * inv(ma.factorial(r)) * inv(ma.factorial(n-r))
    return ans%MOD

def prime(n):
    ans = []
    for i in range(2, int(n**0.5)+1):
        while not n%i: n //= i; ans.append(i)
    if n != 1: ans.append(n)
    return ans

n,m = map(int,input().split())
cnt = col.Counter(prime(m))

ans = 1
for key,val in cnt.items():
    #ans *= cmb(val + n-1, n-1)
    ans *= comb(val + n-1, n-1, exact=1)
    ans %= MOD
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,M=map(int,input().split())
    d=defaultdict(int)
    x=2
    while M>1:
        if M%x==0:
            d[x]+=1
            M//=x
        else:
            x+=1
    def COMinit(n,MOD):
        fac,finv,inv=[0]*max(2,n+1),[0]*max(2,n+1),[0]*max(2,n+1)
        fac[0]=fac[1]=1
        finv[0]=finv[1]=1
        inv[1]=1
        for i in range(2,(n+1)):
            fac[i]=fac[i-1]*i%MOD
            inv[i]=MOD-inv[MOD%i]*(MOD//i)%MOD
            finv[i]=finv[i-1]*inv[i]%MOD
        return fac,finv,inv
    
    fac,finv,inv=COMinit(N*2,MOD)
    
    def COM(n, k, MOD=MOD):
        if n<k or n<0 or k<0:
            return 0
        return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD
    
    ans=1
    for v in d.values():
        ans*=COM(N-1+v,v,MOD)
        ans%=MOD
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

import sys
import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
        
    class Eratos:
        def __init__(self, num):
            assert(num >= 1)
            self.table_max = num
            # self.table[i] は i が素数かどうかを示す (bool)
            self.table = [False if i == 0 or i == 1 else True for i in range(num+1)]
            for i in range(2, int(math.sqrt(num)) + 1):
                if self.table[i]:
                    for j in range(i ** 2, num + 1, i):    # i**2 からスタートすることで定数倍高速化できる
                        self.table[j] = False
            # self.table_max 以下の素数を列挙したリスト
            self.prime_numbers = [2] if self.table_max >= 2 else []
            for i in range(3, self.table_max + 1, 2):
                if self.table[i]:
                    self.prime_numbers.append(i)
        
        def is_prime(self, num):
            """
            >>> e = Eratos(100)
            >>> [i for i in range(1, 101) if e.is_prime(i)]
            [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
            """
            assert(num >= 1)
            if num > self.table_max:
                raise ValueError('Eratos.is_prime(): exceed table_max({}). got {}'.format(self.table_max, num))
            return self.table[num]
        
        def prime_factorize(self, num):
            """
            >>> e = Eratos(10000)
            >>> e.prime_factorize(6552)
            {2: 3, 3: 2, 7: 1, 13: 1}
            """
            assert(num >= 1)
            if int(math.sqrt(num)) > self.table_max:
                raise ValueError('Eratos.prime_factorize(): exceed prime table size. got {}'.format(num))
            factorized_dict = dict()    # 素因数分解の結果を記録する辞書
            candidate_prime_numbers = [i for i in range(2, int(math.sqrt(num)) + 1) if self.is_prime(i)]
            # n について、√n 以下の素数で割り続けると最後には 1 or 素数となる
            # 背理法を考えれば自明 (残された数が √n より上の素数の積であると仮定。これは自明に n を超えるため矛盾)
            for p in candidate_prime_numbers:
                # これ以上調査は無意味
                if num == 1:
                    break
                while num % p == 0:
                    num //= p
                    try:
                        factorized_dict[p]
                    except KeyError:
                        factorized_dict[p] = 0
                    finally:
                        factorized_dict[p] += 1
            if num != 1:
                factorized_dict[num] = 1
            return factorized_dict
    

    n, m = mi()
    eratos = Eratos(n)
    d = eratos.prime_factorize(m)
    # print(d)

    FACT = [1] * (n + int(math.log2(m)) + 1)
    for i in range(2, n + int(math.log2(m)) + 1):
        FACT[i] = (FACT[i-1] * i) % mod
    
    def comb(n, r, m):
        numerator = FACT[n]
        denominator = pow(FACT[n-r] * FACT[r], m - 2, m)
        return (numerator * denominator) % m

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


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

import sys
import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
        
    class Eratos:
        def __init__(self, num):
            assert(num >= 1)
            self.table_max = num
            # self.table[i] は i が素数かどうかを示す (bool)
            self.table = [False if i == 0 or i == 1 else True for i in range(num+1)]
            for i in range(2, int(math.sqrt(num)) + 1):
                if self.table[i]:
                    for j in range(i ** 2, num + 1, i):    # i**2 からスタートすることで定数倍高速化できる
                        self.table[j] = False
            # self.table_max 以下の素数を列挙したリスト
            self.prime_numbers = [2] if self.table_max >= 2 else []
            for i in range(3, self.table_max + 1, 2):
                if self.table[i]:
                    self.prime_numbers.append(i)
        
        def is_prime(self, num):
            """
            >>> e = Eratos(100)
            >>> [i for i in range(1, 101) if e.is_prime(i)]
            [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
            """
            assert(num >= 1)
            if num > self.table_max:
                raise ValueError('Eratos.is_prime(): exceed table_max({}). got {}'.format(self.table_max, num))
            return self.table[num]
        
        def prime_factorize(self, num):
            """
            >>> e = Eratos(10000)
            >>> e.prime_factorize(6552)
            {2: 3, 3: 2, 7: 1, 13: 1}
            """
            assert(num >= 1)
            if int(math.sqrt(num)) > self.table_max:
                raise ValueError('Eratos.prime_factorize(): exceed prime table size. got {}'.format(num))
            factorized_dict = dict()    # 素因数分解の結果を記録する辞書
            candidate_prime_numbers = [i for i in range(2, int(math.sqrt(num)) + 1) if self.is_prime(i)]
            # n について、√n 以下の素数で割り続けると最後には 1 or 素数となる
            # 背理法を考えれば自明 (残された数が √n より上の素数の積であると仮定。これは自明に n を超えるため矛盾)
            for p in candidate_prime_numbers:
                # これ以上調査は無意味
                if num == 1:
                    break
                while num % p == 0:
                    num //= p
                    try:
                        factorized_dict[p]
                    except KeyError:
                        factorized_dict[p] = 0
                    finally:
                        factorized_dict[p] += 1
            if num != 1:
                factorized_dict[num] = 1
            return factorized_dict
    

    n, m = mi()
    eratos = Eratos(n)
    d = eratos.prime_factorize(m)
    # print(d)

    FACT = [1] * (2 * int(math.log2(m)) + 1)
    for i in range(2, 2 * int(math.log2(m)) + 1):
        FACT[i] = (FACT[i-1] * i) % mod
    
    def comb(n, r, m):
        numerator = FACT[n]
        denominator = pow(FACT[n-r] * FACT[r], m - 2, m)
        return (numerator * denominator) % m

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


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

import sys
import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
        
    class Eratos:
        def __init__(self, num):
            assert(num >= 1)
            self.table_max = num
            # self.table[i] は i が素数かどうかを示す (bool)
            self.table = [False if i == 0 or i == 1 else True for i in range(num+1)]
            for i in range(2, int(math.sqrt(num)) + 1):
                if self.table[i]:
                    for j in range(i ** 2, num + 1, i):    # i**2 からスタートすることで定数倍高速化できる
                        self.table[j] = False
            # self.table_max 以下の素数を列挙したリスト
            self.prime_numbers = [2] if self.table_max >= 2 else []
            for i in range(3, self.table_max + 1, 2):
                if self.table[i]:
                    self.prime_numbers.append(i)
        
        def is_prime(self, num):
            """
            >>> e = Eratos(100)
            >>> [i for i in range(1, 101) if e.is_prime(i)]
            [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
            """
            assert(num >= 1)
            if num > self.table_max:
                raise ValueError('Eratos.is_prime(): exceed table_max({}). got {}'.format(self.table_max, num))
            return self.table[num]
        
        def prime_factorize(self, num):
            """
            >>> e = Eratos(10000)
            >>> e.prime_factorize(6552)
            {2: 3, 3: 2, 7: 1, 13: 1}
            """
            assert(num >= 1)
            if int(math.sqrt(num)) > self.table_max:
                raise ValueError('Eratos.prime_factorize(): exceed prime table size. got {}'.format(num))
            factorized_dict = dict()    # 素因数分解の結果を記録する辞書
            candidate_prime_numbers = [i for i in range(2, int(math.sqrt(num)) + 1) if self.is_prime(i)]
            # n について、√n 以下の素数で割り続けると最後には 1 or 素数となる
            # 背理法を考えれば自明 (残された数が √n より上の素数の積であると仮定。これは自明に n を超えるため矛盾)
            for p in candidate_prime_numbers:
                # これ以上調査は無意味
                if num == 1:
                    break
                while num % p == 0:
                    num //= p
                    try:
                        factorized_dict[p]
                    except KeyError:
                        factorized_dict[p] = 0
                    finally:
                        factorized_dict[p] += 1
            if num != 1:
                factorized_dict[num] = 1
            return factorized_dict
    

    n, m = mi()
    eratos = Eratos(n)
    d = eratos.prime_factorize(m)
    # print(d)

    FACT = [1] * (2 * n + 1)
    for i in range(2, 2 * n + 1):
        FACT[i] = (FACT[i-1] * i) % mod
    
    def comb(n, r, m):
        numerator = FACT[n]
        denominator = pow(FACT[n-r] * FACT[r], m - 2, m)
        return (numerator * denominator) % m

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


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

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

def prime_factor(n):
    ass = []
    for i in range(2,int(n**0.5)+1):
        count=0
        while n % i==0:
            count+=1
            n = n//i
        if count!=0:
            ass.append((i,count))
    if n != 1:
        ass.append((n,1))
    return ass


ass = prime_factor(m)
ans = 1
for i, amount in ass:
  ans = ans * len(itertools.combinations_with_replacement(range(n-1),amount)) % mod
print(ans)
# print(ass)

Submission status: Runtime Error

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

MOD = 10**9+7

class Comb:
    def __init__(self, N):
        self.fac = [1] * (N+1)
        for i in range(2, N+1): self.fac[i] = self.fac[i-1] * i % MOD

    def pow(self, a, b):
        res = 1
        while b:
            if b & 1: res = res * a % MOD
            a = a**2 % MOD
            b >>= 1
        return res

    def comb(self, n, r):
        if r < 0 or r > n: return 0
        return (self.fac[n] * self.pow(self.fac[r], MOD-2)) % MOD * self.pow(self.fac[n-r], MOD-2) % MOD

    def permutation(self, n, r):
        if r == 0: return 1
        return self.fac[n] * self.pow(self.fac[n-r], MOD-2) % MOD

from collections import *
def get_prime(n):
    c = Counter()

    while not n % 2:
        c[2] += 1
        n //= 2
    i = 3

    while i**2 <= n:
        while not n % i:
            c[i] += 1
            n //= i
        i += 2

    if n > 1: 
        c[n] += 1

    return c

prime = get_prime(M)
comb = Comb(N+max([m for m in prime.values()]))

ans = 1

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