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:
# 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_max = int(math.log2(M))

M_tmp = M
ips = []
for p in range(2, p_max + 1):
    # how many times M_tmp can be divided
    p_tmp = p
    for i_p in range(ip_max + 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

# create memo
## init
ip_max = max(ips)
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 = 1
    vals = list(memo[i - 1])[::-1]
    p_memo = memo[i]
    for j, val in enumerate(vals[1:]):
        sum_tmp += val
        p_memo[N - 2 - j] = sum_tmp

# calculate ans
ans = 1
for i_p in ips: ans = (ans * distribute(0, i_p, i_p)) % (10 ** 9 + 7) # oh...
    
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_max = int(math.log2(M))

M_tmp = M
ips = []
for p in range(2, p_max + 1):
    # how many times M_tmp can be divided
    p_tmp = p
    for i_p in range(ip_max + 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
    # # ans update (dp)
    # ## expand memo if necessary
    # if i_p > ip_tmp:
    #     for i in range(ip_tmp + 1, i_p + 1):
    #         memo_tmp = [0] * N
    #         sum_tmp = 0 # memo[i - 1][N - 1]
    #         vals = list(memo[i - 1])[::-1]
    #         for j, val in enumerate(vals):
    #             sum_tmp += val
    #             memo_tmp[N - 1 - j] = sum_tmp
    #         memo[i] = list(memo_tmp)
    # ## search and count
    # ans_tmp = distribute(0, i_p, i_p)
    # ## add
    # ans = (ans * ans_tmp) % (10 ** 9 + 7)
    # calculate later
    ips.append(i_p)
    # next
    M_tmp = M_tmp // (p_tmp // p)
    if M_tmp == 1: break

# create memo
## init
ip_max = max(ips)
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 = 1
    vals = list(memo[i - 1])[::-1]
    p_memo = memo[i]
    for j, val in enumerate(vals[1:]):
        sum_tmp += val
        p_memo[N - 2 - j] = sum_tmp

# calculate ans
ans = 1
for i_p in ips: ans = (ans * distribute(0, i_p, i_p)) % (10 ** 9)

    
print(ans)

Submission status: Runtime Error

Solution code:
mod = 1000000007

# nの素因数分解

def prime(n):
    d = []
    i = 2
    while n != 1:
        s = 0
        while n % i == 0:
            n /= i
            s += 1
        d.append(s)
        i += 1
    return d

# xのn乗を計算する
def mod_pow(x, n):
    if n == 1:
        return x
    elif n % 2 == 0:
        half_x = mod_pow(x, n // 2)
        return half_x * half_x % mod
    else:
        return x * mod_pow(x, n-1) % mod

fact = [0] * 100099
inv = [0] * 100099
frac[0] = 1
inv[0] = 1
for k in range(1, 100099):
    fact[k] = fact[k-1] * k % mod
    inv[k] = mod_pow(fact[k], mod-2)

def nCr(n, r):
    return fact[n] * inv[r] % mod * inv[n-r] % mod

def solve():
    N, M = map(int, input().split())
    p = prime(M)
    s = 1
    for i in p:
        s *= nCr(i + N - 1, N - 1)
        s %= mod
    print(s)

solve()

Submission status: Runtime Error

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

mod = 1000000007

f = [] # 素因数分解(指数部のみ)

for p in range(2, M): # 素因数分解
    e = 0
    while M%p == 0:
        e += 1
        M /= p
    
    if e>0:
        f.append(e)
    
    if M == 1:
        break

def pw(a, e):
    if e == 1:
        return a
    p = pw(a, e // 2)
    if e%2 == 1:
        return p * p % mod a % mod
    else:
        return p * p % mod

# fact, inv の計算
fact = [1] * 100040
inv = [1] * 100040
for k in range(1, 100040):
    fact[k] = fact[k-1] * k % mod
    inv[k] = pw(fact[k], mod-2)

ans = 1
for e in f:
    ans = ans * fact[e+N-1] % mod * inv[e] % mod * inv[N-1] % mod # N_H_e (重複組合せ)

print(ans)

Submission status: Runtime Error

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

mod = 1000000007

f = [] # 素因数分解(指数部のみ)

for p in range(2, M): # 素因数分解
    e = 0
    while M%p == 0:
        e += 1
        M /= p
    
    if e>0:
        f.append(e)
    
    if M == 1:
        break

def pw(a, e):
    if e == 1:
        return a
    p = pw(a, e // 2)
    if e%2 == 1:
        return p * p % mod * a % mod
    else:
        return p * p % mod

# fact, inv の計算
fact = [1] * 100033
inv = [1] * 100033
for k in range(1, 100033):
    fact[k] = fact[k-1] * k % mod
    inv[k] = pw(fact[k], mod-2))

def combine(n, k):
    return fact[n] * inv[k] % mod * inv[n-k] % mod

ans = 1
for e in f:
    ans *= combine(e+N-1, e) # N_H_e (重複組合せ)
    ans %= 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):
    # read memo
    if memo[pos][tmp] != None: return memo[pos][tmp]
    # end
    if tmp == 0: return 1
    # next
    ret = 0
    if pos < N - 1:
        for i in range(tmp + 1): ret += distribute(pos + 1, full, tmp - i)
    else: ret += 1
    # print("###", pos, tmp, ret)
    # write memo
    if memo[pos][tmp] != None: memo[pos][tmp] = ret
    return ret

# define search range
p_max = int(M / 2) # M is prime if M has a factor p (> p_max)
ip_max = int(math.log2(M))
memo = [[None] * (ip_max + 1) for i in range(N)] # max ip

M_tmp = M
ans = 1
for p in range(2, p_max + 1):
    # how many times M_tmp can be divided
    p_tmp = p
    for i_p in range(ip_max + 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
    # ans update (dp)
    ## search and count
    ans_tmp = distribute(0, i_p, i_p)
    ## add
    ans = (ans * ans_tmp) % (10 ** 9 + 7)
    # next
    M_tmp = M_tmp // (p_tmp // p)
    if M_tmp == 1: break

print(ans)

Submission status: Runtime Error

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


def distribute(pos, full, tmp):
    # read memo
    if memo[pos][tmp] != None: return memo[pos][tmp]
    # end
    if tmp == 0: return 1
    # next
    ret = 0
    if pos < N - 1:
        for i in range(tmp + 1): ret += distribute(pos + 1, full, tmp - i)
    else: ret += 1
    # print("###", pos, tmp, ret)
    # write memo
    if memo[pos][tmp] != None: memo[pos][tmp] = ret
    return ret

# define search range
p_max = int(math.sqrt(M)) + 1
ip_max = int(math.log2(p_max))
memo = [[None] * (ip_max + 1) for i in range(N)] # max ip

M_tmp = M
ans = 1
for p in range(2, p_max + 1):
    # how many times M_tmp can be divided
    p_tmp = p
    for i_p in range(ip_max + 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
    # ans update (dp)
    ## search and count
    ans_tmp = distribute(0, i_p, i_p)
    ## add
    ans = (ans * ans_tmp) % (10 ** 9 + 7)
    # next
    M_tmp = M_tmp // (p_tmp // p)
    if M_tmp == 1: break

print(ans)

Submission status: Runtime Error

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

# primes = [2, 3, 5, 7, 11, 13, 17]

# M_tmp = M
# factors = []
# for p in primes:
#     for i_p in range(32):
#         if M_tmp % (p ** (i_p + 1)) > 0: break
#     if i_p > 0: factors.append((p, i_p))
#     M_tmp = M_tmp // (p ** i_p)

## memo
memo = [[None] * 33 for i in range(N)] # max ip

def distribute(pos, full, tmp):
    # read memo
    if memo[pos][tmp] != None: return memo[pos][tmp]
    # end
    if tmp == 0: return 1
    # next
    ret = 0
    if pos < N - 1:
        for i in range(tmp + 1): ret += distribute(pos + 1, full, tmp - i)
    else: ret += 1
    # print("###", pos, tmp, ret)
    # write memo
    if memo[pos][tmp] != None: memo[pos][tmp] = ret
    return ret

# ans = 1
# for p, i_p in factors:
#     tmp = distribute(0, i_p, i_p)
#     ans = ans * tmp
#     # print("#", p, tmp)

M_tmp = M
ans = 1
for p in range(2, 2 ** 32):
    # how many times M_tmp can be divided
    for i_p in range(33):
        if M_tmp % (p ** (i_p + 1)) > 0: break
    # escape if M_tmp cannot be divided
    # print("#", p, i_p)
    if i_p < 1: continue
    # ans update (dp)
    ## search and count
    ans_tmp = distribute(0, i_p, i_p)
    # print("###", ans_tmp)
    ## add
    ans = (ans * ans_tmp) % (10 ** 9 + 7)
    # next
    M_tmp = M_tmp // (p ** i_p)
    if M_tmp == 1: break # oh...

print(ans)

Submission status: Runtime Error

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

# primes = [2, 3, 5, 7, 11, 13, 17]

# M_tmp = M
# factors = []
# for p in primes:
#     for i_p in range(32):
#         if M_tmp % (p ** (i_p + 1)) > 0: break
#     if i_p > 0: factors.append((p, i_p))
#     M_tmp = M_tmp // (p ** i_p)

## memo
memo = [[None] * 33 for i in range(N)] # max ip

def distribute(pos, full, tmp):
    # read memo
    if memo[pos][tmp] != None: return memo[pos][tmp]
    # end
    if tmp == 0: return 1
    # next
    ret = 0
    if pos < N - 1:
        for i in range(tmp + 1): ret += distribute(pos + 1, full, tmp - i)
    else: ret += 1
    # print("###", pos, tmp, ret)
    # write memo
    if memo[pos][tmp] != None: memo[pos][tmp] = ret
    return ret

# ans = 1
# for p, i_p in factors:
#     tmp = distribute(0, i_p, i_p)
#     ans = ans * tmp
#     # print("#", p, tmp)

M_tmp = M
ans = 1
for p in range(2, 2 ** 32):
    # how many times M_tmp can be divided
    for i_p in range(33):
        if M_tmp % (p ** (i_p + 1)) > 0: break
    # escape if M_tmp cannot be divided
    # print("#", p, i_p)
    if i_p < 1: continue
    # ans update (dp)
    ## search and count
    ans_tmp = distribute(0, i_p, i_p)
    # print("###", ans_tmp)
    ## add
    ans = (ans * ans_tmp) % (10 ** 9 + 7)
    # next
    M_tmp = M_tmp // (p ** i_p)

print(ans)

Submission status: Runtime Error

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

# primes = [2, 3, 5, 7, 11, 13, 17]

# M_tmp = M
# factors = []
# for p in primes:
#     for i_p in range(32):
#         if M_tmp % (p ** (i_p + 1)) > 0: break
#     if i_p > 0: factors.append((p, i_p))
#     M_tmp = M_tmp // (p ** i_p)

## memo
memo = [[None] * 33 for i in range(N)] # max ip

def distribute(pos, full, tmp):
    # read memo
    if memo[pos][tmp] != None: return memo[pos][tmp]
    # end
    if tmp == 0: return 1
    # next
    ret = 0
    if pos < N - 1:
        for i in range(tmp + 1): ret += distribute(pos + 1, full, tmp - i)
    else: ret += 1
    # print("###", pos, tmp, ret)
    # write memo
    if memo[pos][tmp] != None: memo[pos][tmp] = ret
    return ret

# ans = 1
# for p, i_p in factors:
#     tmp = distribute(0, i_p, i_p)
#     ans = ans * tmp
#     # print("#", p, tmp)

M_tmp = M
ans = 1
for p in range(2, 4):
    # how many times M_tmp can be divided
    for i_p in range(33):
        if M_tmp % (p ** (i_p + 1)) > 0: break
    # escape if M_tmp cannot be divided
    # print("#", p, i_p)
    if i_p < 1: continue
    # ans update (dp)
    ## search and count
    ans_tmp = distribute(0, i_p, i_p)
    # print("###", ans_tmp)
    ## add
    ans = (ans * ans_tmp) % (10 ** 9 + 7)
    # next
    M_tmp = M_tmp // (p ** i_p)

print(ans)

Submission status: Runtime Error

Solution code:
from math import sqrt
from scipy.special import comb

def cal_factors(num):
    factors = {}
    maxmod = int(sqrt(num)) + 1
    for mod in range(2, maxmod):
        i = 0
        while True:
            d, q = divmod(num, mod)
            if q == 0:
                num = d
                i += 1
                factors[mod] = i
            else:
                break

    if num > 1:
        factors[num] = 1

    return factors


n, m = [int(v) for v in input().split()]

mod = 1000000000 + 7
factors = cal_factors(m)
ans = 1
for v in factors.values():
    ans *= comb(v + n - 1, v, exact=True) % mod
    ans %= mod

print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Sep 23 22:00:37 2018
ABC110D
@author: maezawa
"""
import collections

def comb(n, r):
    if n == 0 or r == 0:
        return 1
    return comb(n, r-1)*(n-r+1)//r

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

mod = 10**9+7
np = int(10**4.5 + 10)
is_prime = [True]*(np+1)

is_prime[0] = False
is_prime[1] = False

for i in range(2, np//2):
    if is_prime[i] == True:
        for j in range(2*i,np+1,i):
            is_prime[j] = False

prime_numbers = [i for i in range(np+1) if is_prime[i]]

pds = []
for i in prime_numbers:
    if i > m//2:
        break
    md = m
    while md%i == 0:
        pds.append(i)
        md = md//i
    if md > np:
        pds.append(md)
if pds == []:
    pds.append(m)

#print(pds)
cpds = collections.Counter(pds)
#print(cpds)
ans = 1
for i in cpds.values():
    ans = ans*comb(n+i-1,i)%mod

print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
pem=1
if m==1:
    print(1)
    pem=-1
def fctr2(n): #それぞれの素因数の指数だけ出力
    f=[]
    c=0
    r=int(n**0.5)
    for i in range(2,r+2):
        while n%i==0:
            c+=1
            n=n//i
        if c!=0:
            f.append(c)
            c=0
    if n!=1:
        f.append(1)
    return f

mod=10**9+7
fuc=[1]
def fucfun(n):
    for i in range(1,n):
        e=fuc[i-1]*i
        fuc.append(e%mod)
def com(n,k):
    com=(fuc[n]%mod)*pow(fuc[k],mod-2,mod)*pow(fuc[n-k],mod-2,mod)
    return com
f=fctr2(m)
a=max(f)+n
fucfun(a)
s=1
for i in range(len(f)):
    t=com(f[i]+n-1,f[i])
    s=(s*t)%mod
if pem==1:
    print(s)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
def fctr2(n): #それぞれの素因数の指数だけ出力
    f=[]
    c=0
    r=int(n**0.5)
    for i in range(2,r+2):
        while n%i==0:
            c+=1
            n=n//i
        if c!=0:
            f.append(c)
            c=0
    if n!=1:
        f.append(1)
    return f

mod=10**9+7
fuc=[1]
def fucfun(n):
    for i in range(1,n):
        e=fuc[i-1]*i
        fuc.append(e%mod)
def com(n,k):
    com=(fuc[n]%mod)*pow(fuc[k],mod-2,mod)*pow(fuc[n-k],mod-2,mod)
    return com
f=fctr2(m)
a=max(f)+n
fucfun(a)
s=1
for i in range(len(f)):
    t=com(f[i]+n-1,f[i])
    s=(s*t)%mod
print(s)

Submission status: Runtime Error

Solution code:
import math
n,m = map(int, input().split())
mod = 1000000007
fact = [1]*(n+n+1)
rfact = [1]*(n+n+1)
for i in range(n+n):
    fact[i+1] = rr = ((i+1) * fact[i]) % mod
    rfact[i+1] = pow(rr, mod-2, mod)
def comb(N, K,mod):
    return fact[N] * rfact[K] * rfact[N-K] % mod
def make_prime_list_2(num):
    if num < 2:
        return []

    # 0のものは素数じゃないとする
    prime_list = [i for i in range(num + 1)]
    prime_list[1] = 0 # 1は素数ではない
    num_sqrt = math.sqrt(num)

    for prime in prime_list:
        if prime == 0:
            continue
        if prime > num_sqrt:
            break

        for non_prime in range(2 * prime, num, prime):
            prime_list[non_prime] = 0

    return [prime for prime in prime_list if prime != 0]
def prime_factorization_2(num):
    if num <= 1:
        print(1)
        exit()
        return False
    else:
        num_sqrt = math.floor(math.sqrt(num))
        prime_list = make_prime_list_2(num_sqrt)

        dict_counter = {}
        for prime in prime_list:
            while num % prime == 0:
                if prime in dict_counter:
                    dict_counter[prime] += 1
                else:
                    dict_counter[prime] = 1
                num //= prime
        if num != 1:
            if num in dict_counter:
                dict_counter[num] += 1
            else:
                dict_counter[num] = 1

        return dict_counter
x = prime_factorization_2(m)
x = list(x.values())
ans = 1
for i in x:
  ans*= comb(i+n-1,i,mod)
  ans %=mod
print(ans)

Submission status: Runtime Error

Solution code:
import math
mod = 1000000007
def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*pow(b,p-2,p)*pow(c,p-2,p))%p
n,m = map(int, input().split())
def make_prime_list_2(num):
    if num < 2:
        return []

    # 0のものは素数じゃないとする
    prime_list = [i for i in range(num + 1)]
    prime_list[1] = 0 # 1は素数ではない
    num_sqrt = math.sqrt(num)

    for prime in prime_list:
        if prime == 0:
            continue
        if prime > num_sqrt:
            break

        for non_prime in range(2 * prime, num, prime):
            prime_list[non_prime] = 0

    return [prime for prime in prime_list if prime != 0]
def prime_factorization_2(num):
    if num <= 1:
        return False
    else:
        num_sqrt = math.floor(math.sqrt(num))
        prime_list = make_prime_list_2(num_sqrt)

        dict_counter = {}
        for prime in prime_list:
            while num % prime == 0:
                if prime in dict_counter:
                    dict_counter[prime] += 1
                else:
                    dict_counter[prime] = 1
                num //= prime
        if num != 1:
            if num in dict_counter:
                dict_counter[num] += 1
            else:
                dict_counter[num] = 1

        return dict_counter
x = prime_factorization_2(m)
x = list(x.values())
ans = 1
for i in x:
  ans*= comb(i+n-1,i,mod)
  ans %=mod
print(ans)

Submission status: Runtime Error

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

#x以下の素数の列挙   
import math
x=math.floor(math.sqrt(10**9))
L=math.floor(math.sqrt(x))#平方根を求める
Primelist=[i for i in range(x+1)]
Primelist[1]=0#素数でないものは0にする.
for i in Primelist:
    if i>L:
        break
    if i==0:
        continue
    for j in range(2*i,x+1,i):
        Primelist[j]=0
Primes=[Primelist[j] for j in range(x+1) if Primelist[j]!=0]

#素因数分解
DICT=dict()
i=0
while M!=1:
    if M%Primes[i]==0:
        DICT[i]=DICT.get(i,0)+1
        M=M//Primes[i]
    else:
        i+=1

def Combi2(a,b):#aは大きいが、bは小さいとき
    ANS=1
    for i in range(min(b,a-b)):
        ANS=ANS*(a-i)%mod*pow(b-i,mod-2,mod)%mod

    return ANS%mod


ANS=1
for i in DICT.values():
    ANS=ANS*Combi2(N-1+i,i)%mod

print(ANS)

Submission status: Runtime Error

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

#x以下の素数の列挙   
import math
x=math.floor(math.sqrt(10**9))
L=math.floor(math.sqrt(x))#平方根を求める
Primelist=[i for i in range(x+1)]
Primelist[1]=0#素数でないものは0にする.
for i in Primelist:
    if i>L:
        break
    if i==0:
        continue
    for j in range(2*i,x+1,i):
        Primelist[j]=0
Primes=[Primelist[j] for j in range(x+1) if Primelist[j]!=0]

#素因数分解
LISTS=[0 for i in range(4000)]
i=0
while M!=1:
    if M%Primes[i]==0:
        LISTS[i]+=1
        M=M//Primes[i]
    else:
        i+=1

def Combi2(a,b):#aは大きいが、bは小さいとき
    ANS=1
    for i in range(min(b,a-b)):
        ANS=ANS*(a-i)%mod*pow(b-i,mod-2,mod)%mod

    return ANS%mod


ANS=1
for i in range(4000):
    if LISTS[i]>=1:
        ANS=ANS*Combi2(N-1+LISTS[i],LISTS[i])%mod

print(ANS)

Submission status: Runtime Error

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

#x以下の素数の列挙   
import math
x=math.floor(math.sqrt(10**9))
L=math.floor(math.sqrt(x))#平方根を求める
Primelist=[i for i in range(x+1)]
Primelist[1]=0#素数でないものは0にする.
for i in Primelist:
    if i>L:
        break
    if i==0:
        continue
    for j in range(2*i,x+1,i):
        Primelist[j]=0
Primes=[Primelist[j] for j in range(x+1) if Primelist[j]!=0]

#素因数分解
LISTS=[0 for i in range(4000)]
i=0
while M!=1:
    if M%Primes[i]==0:
        LISTS[i]+=1
        M=M//Primes[i]
    else:
        i+=1

def Combi2(a,b):#aは大きいが、bは小さいとき
    ANS=1
    for i in range(min(b,a-b)):
        ANS=ANS*(a-i)*pow(b-i,mod-2,mod)

    return ANS%mod


ANS=1
for i in range(len(LISTS)):
    if LISTS[i]>=1:
        ANS=ANS*Combi2(N-1+LISTS[i],LISTS[i])%mod

print(ANS)

Submission status: Runtime Error

Solution code:
import sympy

# aのp乗を求めるアルゴリズム
def modpow(a, p):
    if p == 0:
        return 1
    if p%2 == 0:
        halfp = p/2
        half = modpow(a, p/2)
        return half**2 % mod
    else:
        return a * modpow(a, p-1) % mod

def calc_comb(a, b):
    if b > a-b:
        return calc_comb(a, a-b)
    else:
        ans_mul = 1
        ans_div = 1
        for i in range(0,b):
            ans_mul *= a-i
            ans_div *= i+1
            ans_mul %= mod
            ans_div %= mod
    # ans_mul / ans_div を逆元を使って求める
    ans = ans_mul * modpow(ans_div, mod-2)
    return ans

mod = 10**9+7
n, m = map(int, input().split())

dic = sympy.factorint(m)

ans = 1
for i in dic.values():
    ans *= calc_comb(n+i-1, n-1)
    ans %= mod

print(ans)

Submission status: Runtime Error

Solution code:
import collections
def kaijo(x):
    a=1
    for i in range(1,x+1):
        a*=i
    return a
def perm(x,y):
    ans=1
    for i in range(x,x-y,-1):
        ans*=i
    return ans
def com(x,y):
    return perm(x,min(y,x-y))//kaijo(min(y,x-y))

nn,m=map(int,input().split())
x=primes(int(m**0.5+1))
y=[]
z=m
t=1
while(t**2<=m):
    t+=1
    while(z%t==0):
        y.append(t)
        z//=t
if len(y)==0 and m>1:
    y.append(m)
c=collections.Counter(y).values()
ans=1
mod=10**9+7
for t in c:
    ans*=com(t+nn-1,t)
    ans%=mod
print(ans)

Submission status: Runtime Error

Solution code:
    if M == 1:
        return 1

    def prime_factorization_power_list(n):
        i = 2
        table = {}
        while i**2 <= n:
            table[i] = 0
            while n % i == 0:
                table[i] += 1
                n //= i
            if table[i] == 0:
                table.pop(i)
            i += 1
        if n > 1:
            table[n] = 1
        return table

    MOD = 10**9 + 7
    prime_m = prime_factorization_power_list(M)
    b_max = max(prime_m.values())  # 素因数分解の指数の最大値
    # フェルマーの小定理による組合せの計算
    factorial = [1] * (b_max + N)  # (b_i + N - 1)!を計算するため。0!も入れておく
    for k in range(1, b_max + N - 1):
        factorial[k + 1] = (factorial[k] * (k + 1)) % MOD
    # k!のmod 10**9+7における逆元を計算
    fact_inv = [1] * (b_max + N)
    fact_inv[b_max + N - 1] = pow(factorial[b_max + N - 1], MOD - 2, MOD)
    for k in range(b_max + N - 1, 0, -1):
        fact_inv[k - 1] = (fact_inv[k] * k) % MOD

    def nCr(n, r, M):
        if n < 0 or r < 0 or n < r:
            return 0
        else:
            return (factorial[n] * fact_inv[r] * fact_inv[n - r]) % M

    ans = 1
    for b in prime_m.values():
        ans = (ans * nCr(b + N - 1, b, MOD)) % MOD

    return ans

N, M = [int(i) for i in input().split()]
print(d_factorization(N, M))

Submission status: Runtime Error

Solution code:
from math import factorial

def C(n,r):
    return factorial(n)//factorial(r)//factorial(n-r)

def H(n,r):
    return C(n+r-1,r)

def prime_count(n):
    count=[]
    for i in range(2,n): 
        if n==1:
            return count
        if i**2>n:
            count.append(1)
            return count
        if n%i==0:
            t=1
            n//=i
            while True:
                if n%i: break
                else:
                    n //= i
                    t += 1
            count.append(t)
            
N,M=map(int,input().split())
            
ans=1
for num in prime_count(M):
    ans *= H(N,num)
    
print(ans%(10**9+7))

Submission status: Runtime Error

Solution code:
def d_factorization(N, M):
    def prime_factorization_power_list(n):
        i = 2
        table = {}
        while i**2 <= n:
            table[i] = 0
            while n % i == 0:
                table[i] += 1
                n //= i
            if table[i] == 0:
                table.pop(i)
            i += 1
        if n > 1:
            table[n] = 1
        return table

    MOD = 10**9 + 7
    prime_m = prime_factorization_power_list(M)
    b_max = max(prime_m.values())  # 素因数分解の指数の最大値
    # フェルマーの小定理による組合せの計算
    factorial = [1] * (b_max + N)  # (b_i + N - 1)!を計算するため。0!も入れておく
    for k in range(1, b_max + N - 1):
        factorial[k + 1] = (factorial[k] * (k + 1)) % MOD
    # k!のmod 10**9+7における逆元を計算
    fact_inv = [1] * (b_max + N)
    fact_inv[b_max + N - 1] = pow(factorial[b_max + N - 1], MOD - 2, MOD)
    for k in range(b_max + N - 1, 0, -1):
        fact_inv[k - 1] = (fact_inv[k] * k) % MOD

    def nCr(n, r, M):
        if n < 0 or r < 0 or n < r:
            return 0
        else:
            return (factorial[n] * fact_inv[r] * fact_inv[n - r]) % M

    ans = 1
    for b in prime_m.values():
        ans = (ans * nCr(b + N - 1, b, MOD)) % MOD

    return ans

N, M = [int(i) for i in input().split()]
print(d_factorization(N, M))

Submission status: Runtime Error

Solution code:
from math import factorial

def C(n,r):
    return factorial(n)//factorial(r)//factorial(n-r)

def H(n,r):
    return C(n+r-1,r)

def prime_count(n):
    count=[]
    for i in range(2,n): 
        if n==1:
            return count
        if i**2>n:
            count.append(1)
            return count
        if n%i==0:
            t=1
            n//=i
            while True:
                if n%i: break
                else:
                    n //= i
                    t += 1
            count.append(t)
            
N,M=map(int,input().split())
            
ans=1
for num in count(M):
    ans *= H(N,num)
    
print(ans%(10**9+7))

Submission status: Runtime Error

Solution code:
from math import factorial

def C(n,r):
    return factorial(n)//factorial(r)//factorial(n-r)

def H(n,r):
    return C(n+r-1,r)

def prime_count(n):
    count=[]
    for i in range(2,n): 
        if n==1:
            return count
        if i**2>n:
            count.append(1)
            return count
        if n%i==0:
            t=1
            n//=i
            while True:
                if n%i: break
                else:
                    n //= i
                    t += 1
            count.append(t)
            
N,M=map(int,input().split())
            
ans=1
for num in count(M):
    ans *= H(N,num)%(10**9+7)
    
print(ans%(10**9+7))

Submission status: Runtime Error

Solution code:
import math
from math import factorial

def C(n,r):
    return factorial(n)//factorial(r)//factorial(n-r)

def H(n,r):
    return C(n+r-1,r)

def make_prime_list_2(num):
    if num < 2:
        return []

    # 0のものは素数じゃないとする
    prime_list = [i for i in range(num + 1)]
    prime_list[1] = 0 # 1は素数ではない
    num_sqrt = math.sqrt(num)

    for prime in prime_list:
        if prime == 0:
            continue
        if prime > num_sqrt:
            break

        for non_prime in range(2 * prime, num, prime):
            prime_list[non_prime] = 0

    return [prime for prime in prime_list if prime != 0]

def prime_factorization_2(num):
    if num <= 1:
        return False
    else:
        num_sqrt = math.floor(math.sqrt(num))
        prime_list = make_prime_list_2(num_sqrt)

        dict_counter = {}
        for prime in prime_list:
            while num % prime == 0:
                if prime in dict_counter:
                    dict_counter[prime] += 1
                else:
                    dict_counter[prime] = 1
                num //= prime
        if num != 1:
            if num in dict_counter:
                dict_counter[num] += 1
            else:
                dict_counter[num] = 1

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

def count(num):
    cou=[]
    for v in prime_factorization_2(num).values():
        cou.append(v)
    return cou

ans=1
for num in count(M):
    ans *= H(N,num)
    
print(ans%(10**9+7))

Submission status: Runtime Error

Solution code:
from sympy import factorint


def prepare(n, MOD):
    f = 1
    factorials = [1] * (n + 1)
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials[m] = f
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return factorials, invs


MOD = 1000000007
n, m = map(int, input().split())
pf = factorint(m)
mx = max(pf.values())
f, r = prepare(n + mx - 1, MOD)
ans = 1
for p, e in pf.items():
    ans *= f[n + e - 1]
    ans %= MOD
    ans *= r[n - 1]
    ans %= MOD
    ans *= r[e]
    ans %= MOD
print(ans)

Submission status: Runtime Error

Solution code:
import collections
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
def kaijo(x):
    a=1
    for i in range(1,x+1):
        a*=i
    return a
def perm(x,y):
    ans=1
    for i in range(x,x-y,-1):
        ans*=i
    return ans
def com(x,y):
    return perm(x,min(y,x-y))//kaijo(min(y,x-y))

nn,m=map(int,input().split())
x=primes(int(m**0.5+1))
y=[]
z=m
for t in x:
    while(z%t==0):
        z//=t
        y.append(t)
c=list(collections.Counter(y).values())

ans=1
for t in c:
    ans*=com(t+nn-1,t)
    ans%=mod
print(ans)