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:
def factorial(n):
	fact = 1
	while n > 0:
		fact *= n
		n -= 1
	return fact
	
def combination(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))

n, m = map(int, input().split())
n_def = n
natural = list(range(2,320))
index = 0
while index < len(natural):
	for number in natural:
		if number % natural[index] == 0 and number / natural[index] != 1:
			natural.remove(number)
	index += 1
prime = natural

prime_division = {}
index = 0
number_prime = 0
while prime[index] <= m:
	if m % prime[index] == 0:
		m /= prime[index]
		number_prime += 1
		continue		
	else:
		prime_division[prime[index]] = number_prime
		number_prime = 0
		index += 1
else:
	prime_division[prime[index]] = number_prime

list_division = list(prime_division.values())
ans = 1
for i in list_division:
	ans *= combination(i+n-1,n-1)
print(int(ans%(10**9 + 7)))

Submission status: Runtime Error

Solution code:
import math

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

D = {}
m = M
for i in range(2, int M):
    while m % i == 0:
        D[i] = D.get(i,0)+1
        m = m//i

d = []
for v in D.values():
    d.append(v)

tmp = [0] * len(d)
for i in range(len(d)):
    tmp[i] = (math.factorial(N-1+d[i]) // (math.factorial(N-1)*math.factorial(d[i])))%(10**9 + 7)

ans = 1
for i in range(len(tmp)):
    ans = ans*tmp[i]%(10**9 +7)
print(ans)

Submission status: Runtime Error

Solution code:
import sys

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

factor = {}
tmp = 2
while(M // tmp >= 1):
    if(M % tmp != 0):
        if(tmp == 2):
            tmp += 1
        elif(M // tmp < tmp):
            tmp = M
        else:
            tmp += 2
        continue

    M = M // tmp
    factor[tmp] = factor.get(tmp, 0) + 1

if(factor == {}):
    pimport sys

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

factor = {}
tmp = 2
while(M // tmp >= 1):
    if(M % tmp != 0):
        if(tmp == 2):
            tmp += 1rint(1)
    sys.exit()

ans = 1
max_a = 7 + 10 ** 9
max_value = max(list(factor.values()))
aho = {0: 1}
fact = {0: 1}
abc = {}
for i in range(1, max_value + 1):
    # print(i)
    aho[i] = ((aho[i - 1] * (i + N - 1)))
    fact[i] = (fact[i - 1] * i)
    abc[i] = (aho[i] // fact[i]) % max_a


# print(factor)
# print(aho, fact)
for i in factor.values():
    # print(i)
    ans = (ans * abc[i]) % max_a
print(ans)

Submission status: Runtime Error

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

D = {}
m = M
for i in range(2, int(M**0.5)+2):
    while m % i == 0:
        D[i] = D.get(i,0)+1
        m = m//i
if D == {}:
    D[M] = 1

d = []
for v in D.values():
    d.append(v)

tmp = [0] * len(d)
for i in range(len(d)):
    tmp[i] = (math.factorial(N-1+d[i]) // (math.factorial(N-1)*math.factorial(d[i])))%(10**9 + 7)

ans = 1
for i in range(len(tmp)):
    ans = ans*tmp[i]%(10**9 +7)
print(ans)

Submission status: Runtime Error

Solution code:
import math
def combination(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
n, m = map(int, input().split())
n_def = n
natural = list(range(2,400))
index = 0
while index < len(natural):
	for number in natural:
		if number % natural[index] == 0 and number / natural[index] != 1:
			natural.remove(number)
	index += 1
prime = natural

prime_division = {}
index = 0
number_prime = 0
while prime[index] <= m:
	if m % prime[index] == 0:
		m /= prime[index]
		number_prime += 1
		continue		
	else:
		prime_division[prime[index]] = number_prime
		number_prime = 0
		index += 1
else:
	prime_division[prime[index]] = number_prime

list_division = list(prime_division.values())
ans = 1
for i in list_division:
#print(combination(i+n-1,n-1))
	ans *= combination(i+n-1,n-1)
print(int(ans%(10**9 + 7)))

Submission status: Runtime Error

Solution code:
import numpy as np

def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct

def factorial(n):
    if n:
        return n * factorial(n -1)
    else:
        return 1
        
def calc(n,xx):
    r = 1
    for i in range(n,n+xx):
        r *= i
    return(r//factorial(xx))



N,M = map(int,input().split())
fct = np.array(factorize(M))
ans = 1
p = fct.shape[0]
x = fct[:,1]
for i in range(x.shape[0]):
    ans *= calc(N,x[i])
print(int(ans%(10**9+7)))

Submission status: Runtime Error

Solution code:
# coding: utf-8
from sympy.ntheory import factorint
import math

nm = input().split(" ")
n = int(nm[0])
m = int(nm[1])


factors = factorint(m)
answer = 1
for f, e in factors.items():
    answer *= math.factorial(n - 1 + e) // (math.factorial(n - 1) * math.factorial(e))

print(answer % 1000000007)

Submission status: Runtime Error

Solution code:
2 6

Submission status: Runtime Error

Solution code:
import itertools

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]

def fact(M):
    LIST=[]
    i=0
    while M!=1:
        if M%Primes[i]==0:
            LIST.append(Primes[i])
            M=M//Primes[i]
        else:
            i+=1

    PE=list(itertools.product(range(0,2),repeat=len(LIST)))

    SET={1}

    for pe in PE:
        ANS=1

        for j in range(len(LIST)):
            if pe[j]==1:
                ANS=ANS*LIST[j]

  

        SET=SET|{ANS}

    return SET

SET=fact(M)
factor=dict()

for j in SET:
    factor[j]=fact(j)

    
DP=dict()
def dp(n,m):
    if n==1 or m==1:
        return 1
    
    ANS=0
    for j in factor[m]:
        if DP.get((n-1,m//j),-1)!=-1:
            ANS=(ANS+DP[n-1,m//j])%mod
        else:
            ANS=(ANS+dp(n-1,m//j))%mod

    DP[n,m]=ANS%mod
    return ANS
    
for i in range(1,N,10):
    dp(i,M)

print(dp(N,M))

Submission status: Runtime Error

Solution code:
def maketree(n,m, c, dic):
    addl=[]
    addl.clear()
    a=[]
    for i in m:
        if not i in dic:
            addll=[]
            for j in range(1, i+1):
                #print(i,"%",j)
                if i%j==0:
                    addl.append(j)
                    addll.append(j)
            dic[i]=addll
            #print(addll, dic)
        else:
            for j in dic[i]:
                addl.append(j)
    c+=1
    if not c==n-1:
        maketree(n, addl,c,dic)
    else:
        #print(li)
        #print(dic)
        print(len(addl) % (10**9+7))


[n,m]=[int(i) for i in input().split()]
mli=[m]
c=0
dic={}
maketree(n,mli,c,dic)

#print(ans)

Submission status: Runtime Error

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

dp = [[0 for i in range(M+1)] for j in range(N+1)]
def fact(n, m):
  if n == 1:
    return 1
  if dp[n][m] == 0:
    for i in range(1,m+1):
      if m % i != 0:
        continue
      dp[n][m] += fact(n-1,int(m/i))
  return dp[n][m]

print(fact(N,M))

Submission status: Runtime Error

Solution code:
import numpy as np

def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct

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


N,M = map(int,input().split())
fct = np.array(factorize(M))
ans = 1
p = fct.shape[0]
x = fct[:,1]
for i in range(x.shape[0]):
    ans *= (factorial(N+x[i]-1)//factorial(x[i])//factorial(N-1))
print(int(ans%(10**9+7)))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import math
mod = 1000000007

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n;

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p;
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k]) % mod

    return result;

s=input()
N, M = map(int, s.split())
result=1

for i in range(2, int(math.sqrt(N)) + 2):
    c=0
    while N % i == 0:
        N /= i
        c=c+1
        
    if c>0:
        result =result * cmb(N+c-1,c) % mod

print(result)

Submission status: Runtime Error

Solution code:
def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct

import numpy as np
x = 10**9 + 7
def fact(n,m = 1):
    if n > m + 1:
        return n * fact(n-1,m)
    else:
        return n
def fact(n,m = 1):
    if n > m + 1:
        nn, lis = fact(n-1,m)
        return n * nn, lis.append(nn)
    else:
        return n, []

def fact(n,m=1):
    return np.arange(m+1,n+1)
n,m = list(map(int,input().split()))

a = factorize(m)

ss = []
for b in a:
    ss.append(b[1])

# nn = fact(n - 1)
s = 1
lis = []
waru = []
for sss in ss:
#     temp = fact(sss + n - 1, n-1) / fact(sss)
    temp = fact(sss + n - 1, n-1)
    lis.append(temp)
    waru.append(fact(sss))
#     print(temp)
kake = np.hstack(lis)
waru = np.hstack(waru)

# print(s)

s = 1
for w in waru:
    s/=w
for a in kake:
    s *= a
#     print(s)
#     if int(s) == s:
#         s = s%x

print(int(s))

Submission status: Runtime Error

Solution code:
num = (10 ** 9) + 7

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

if n == 1:
    print(1)
    exit()

prime_upper = int(m ** (1/2) + 50)
prime_dict = {}

check = [False] * prime_upper
prime = [2]

while m % 2 == 0:
    m //= 2
    if not 2 in prime_dict.keys():
        prime_dict[2] = 0
    prime_dict[2] += 1

for j in range(2, prime_upper, 2):
    check[j] = True

for i in range(3, prime_upper, 2):
    if not check[i]:
        prime.append(i)
        while m % i == 0:
            m //= i
            if not i in prime_dict.keys():
                prime_dict[i] = 0
            prime_dict[i] += 1

        for j in range(i, prime_upper, i):
            check[j] = True

if len(prime_dict.values()) != 0:
    value_max = max(prime_dict.values())
    com2 = [[0] * (value_max + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, value_max + 1):
            if i == 1:
                com2[i][j] = 1
            elif j == 1:
                com2[i][j] = i
            else:
                com2[i][j] = (com2[i][j - 1] + com2[i - 1][j]) % num
    if m != 1:
        ans = n
    else:
        ans = 1
    for key, value in prime_dict.items():
        ans = (ans * com2[n][value]) % num
else:
    print(n)

print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import math
mod = 1000000007

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n;

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p;
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k]) % mod

    return result;

s=input()
N, M = map(int, s.split())
result=1

for i in range(2, int(math.sqrt(n)) + 2):
    c=0
    while n % i == 0:
        n /= i
        c=c+1
        
    if c>0:
        result =result * cmb(N+c-1,c) % mod

print(result)

Submission status: Runtime Error

Solution code:
# coding: utf-8
import math

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

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


# m の素因数分解
prim_list = []
d = 2
while d*d <= m:
	while (m % d) == 0:
		prim_list.append(d)
		m //= d
	d += 1
if m > 1:
	prim_list.append(m)
print(prim_list)

sisuu_list = []
cnt = 1
target = prim_list[0]
for i in range(1, len(prim_list)):
	if target == prim_list[i]:
		cnt += 1
	else:
		target = prim_list[i]
		sisuu_list.append(cnt)
		cnt = 1
sisuu_list.append(cnt)
print(sisuu_list)

answer = 1
for sisuu in sisuu_list:
	answer *= C((n-1 + sisuu), sisuu)

print(answer)

Submission status: Runtime Error

Solution code:
num = (10 ** 9) + 7

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

prime_upper = int(m ** (1/2) + 50)
prime_dict = {}

check = [False] * prime_upper
prime = [2]

while m % 2 == 0:
    m //= 2
    if not 2 in prime_dict.keys():
        prime_dict[2] = 0
    prime_dict[2] += 1

for j in range(2, prime_upper, 2):
    check[j] = True

for i in range(3, prime_upper, 2):
    if not check[i]:
        prime.append(i)
        while m % i == 0:
            m //= i
            if not i in prime_dict.keys():
                prime_dict[i] = 0
            prime_dict[i] += 1

        for j in range(i, prime_upper, i):
            check[j] = True

value_max = max(prime_dict.values())
com2 = [[0] * (value_max + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, value_max + 1):
        if i == 1:
            com2[i][j] = 1
        elif j == 1:
            com2[i][j] = i
        else:
            com2[i][j] = (com2[i][j - 1] + com2[i - 1][j]) % num
if m != 1:
    ans = n
else:
    ans = 1
for key, value in prime_dict.items():
    ans = (ans * com2[n][value]) % num

print(ans)

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
MOD = 10**9+7
import math
import sys

sys.setrecursionlimit(100000)
n,m=[int(i) for i in input().split()]

yaku = set()
for i in range(1,math.floor(math.sqrt(m+1))+2):
    if m%i ==0:
        yaku.add(i)

cc=[]
for i in yaku:
    cc.append(m//i)
for i in cc:
    yaku.add(i)

memo = {}
def func(p,q):
    c=0
    if q==1:
        return 1
    for i in yaku:
        if p%i != 0:
            continue
        if (p//i,q-1) not in memo:
            k=func(p//i,q-1)%MOD
            c+=k%MOD
            memo[(p//i,q-1)]=k
        else: 
            c+= memo[(p//i,q-1)] % MOD
    return c
        
    
#print(yaku)
print(func(m,n))
#print(memo)

Submission status: Runtime Error

Solution code:
import math
mod = 1000000007

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n;

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p;
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k]) % mod

    return result;


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

for i in xrange(2, int(math.sqrt(n)) + 2):
    c=0
    while n % i == 0:
        n /= i
        c=c+1
        
    if c>0:
        result =result * cmb(N+c-1,c) % mod

print(result)

Submission status: Runtime Error

Solution code:
import math
N, M = map(int, input().split())
max = int(math.sqrt(M))
mod = 7 + 10**9
F = []
for i in range(1, max+1):
    if M%i == 0:
        F.append(i)
        F.append(M//i)

def DP(i, n, memo = {}): 
    if i == 1 or n==1:
        return 1
    try:
        return memo[(i, n)]
    except KeyError:
        ans = 0
        for j in F:
            if n//j >= 1 and n%j == 0:
                ans += DP(i-1, n//j, memo)
                ans %= mod
        memo[(i, n)] = ans
        return ans

memo = {}
print(DP(N, M, memo))

Submission status: Runtime Error

Solution code:
num = (10 ** 9) + 7

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

prime_upper = int(m ** (1/2) + 10)
prime_dict = {}

check = [False] * prime_upper
prime = [2]

while m % 2 == 0:
    m //= 2
    if not 2 in prime_dict.keys():
        prime_dict[2] = 0
    prime_dict[2] += 1

for j in range(2, prime_upper, 2):
    check[j] = True

for i in range(3, prime_upper, 2):
    if not check[i]:
        prime.append(i)
        while m % i == 0:
            m //= i
            if not i in prime_dict.keys():
                prime_dict[i] = 0
            prime_dict[i] += 1

        for j in range(i, prime_upper, i):
            check[j] = True

value_max = max(prime_dict.values())
com2 = [[0] * (value_max + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, value_max + 1):
        if i == 1:
            com2[i][j] = 1
        elif j == 1:
            com2[i][j] = i
        else:
            com2[i][j] = (com2[i][j - 1] + com2[i - 1][j]) % num
if m != 1:
    ans = n
else:
    ans = 1
for key, value in prime_dict.items():
    ans = (ans * com2[n][value]) % num

print(ans)

Submission status: Runtime Error

Solution code:
a=map(int, raw_input().split())

def b(c, t):
    if t==1:
        return 1
    else:
        cc=0
        for i in range(c):
            if c%(i+1)==0:
                cc += b(c/(i+1),t-1)
        return cc

print b(a[1], a[0])

Submission status: Runtime Error

Solution code:
def maketree(n,m, li, dic):
    addl=[]
    a=[]
    for i in m:
        if not i in dic:
            for j in range(1, i+1):
                #print(i,"%",j)
                if i%j==0:
                    addl.append(j)
            dic[i]=addl
            #print(addl, dic)
        else:
            for i in dic:
                addl.append(i)
    li.append(addl)
    if not len(li)==n-1:
        maketree(n, addl,li,dic)
    else:
        #print(li)
        print(len(li[-1]) % (10**9+7))


[n,m]=[int(i) for i in input().split()]
mli=[m]
li=[]
dic={}
maketree(n,mli,li,dic)

#print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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


def prime_decomposition(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

pr = prime_decomposition(M)
di = defaultdict(int)
for p in pr:
    di[p] += 1

def combination(n, mod):
    lst = [1]
    for i in range(1, n+1):
        lst.append(lst[-1] * (n+1-i) % mod * modinv(i, mod) % mod)
    return lst
mod = 10**9+7
ans = 1
for k, v in di.items():
    ans *= combination(v+N-1, mod)[N-1]
    ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
def maketree(n,m, li):
    addl=[]
    for i in m:
        for j in range(1, i+1):
            #print(i,"%",j)
            if i%j==0:
                addl.append(j)
    li.append(addl)
    if not len(li)==n-1:
        maketree(n, addl,li)
    else:
        #print(li)
        print(len(li[-1]))


[n,m]=[int(i) for i in input().split()]
mli=[m]
li=[]
maketree(n,mli,li)

#print(ans)

Submission status: Runtime Error

Solution code:
one=list(map(int,input().split()))
#print(one)
z=[0]
def multip(begin,goal,time):
    if time == 0 and begin == goal:
        z[0] += 1
        return
    if time==0:
        return 
    #if time==0:
    #    return
    #if begin > goal:
    #    return
    #else:
    for i in range(1,goal+1):
        if time==one[0]:
            multip(i,goal,time-1)
        else:
            if begin<=goal:
                multip(begin*i, goal, time - 1)
            else:
                return
    return
multip(0,one[1],one[0])
print(z[0])

Submission status: Runtime Error

Solution code:
one=list(map(int,input().split()))
#print(one)
z=[0]
def multip(begin,goal,time):
    if time == 0 and begin == goal:
        z[0] += 1
        return
    if time==0:
        return
    if begin > goal:
        return
    else:
        for i in range(1,goal+1):
            if time==one[0]:
                multip(i,goal,time-1)
            else:
                multip(begin*i, goal, time - 1)
    return
multip(0,one[1],one[0])
print(z[0])

Submission status: Runtime Error

Solution code:
import sys
import math
import random

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

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

def C(n, r):
    return P(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 #出力の制限
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 )

def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct

facts = factorize(M)
# print(facts)

ans = 1

for fact in facts:
    a = fact[1]
    ans *= cmb(a+N-1, N-1, mod)
    ans %= 10**9 + 7

print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
def factorial_memo(n, p):
  F = [1] * (n + 1)
  for i in range(n):
    F[i + 1] = F[i] * (i + 1) % p
  return F

def inverse(F, p):
  Finv = [x for x in F]
  Finv[-1] = pow(Finv[-1], p - 2, p)
  for i in range(len(F) - 2, 0, -1):
    Finv[i] = Finv[i + 1] * (i + 1) % p
  return Finv

def comb(*A):
  f = F[sum(A)]
  for a in A:
    f *= Finv[a]
    f %= p
  return f

def is_prime(n):
  for prime in prime_table:
    if n % prime == 0:
      return False
  else:
    return True

N, M = map(int, input().split())
p = 10 ** 9 + 7
prime_table = []
primes = defaultdict(int)
n = 2
while n <= M:
  if is_prime(n):
    prime_table.append(n)
    while M % n == 0:
      primes[n] += 1
      M //= n
  n += 1
F = factorial_memo(max(primes.values()) + N - 1, p)
Finv = inverse(F, p)
cnt = 1
for c in primes.values():
  cnt *= comb(c, N - 1)
  cnt  %= p
print(cnt)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
P=10**9+7
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
def inv(x):
    return egcd(x,P)[0]
Fact=[0 for i in range(2*N+1)]
Finv=[0 for i in range(2*N+1)]
Fact[0]=1
Finv[0]=1
for i in range(2*N):
    Fact[i+1]=(Fact[i]*(i+1))%P
    Finv[i+1]=inv(Fact[i+1])%P
def C(n,k):
    return (Fact[n]*(Finv[k]*Finv[n-k])%P)%P
def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct
D=factorize(M)
ans=1
for seq in D:
    k=seq[1]
    ans=ans*C(k+N-1,N-1)
    ans=ans%P
print(ans)

Submission status: Runtime Error

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

t = {}

while s==0:
    for i in range(2,m+1):
        if m%i==0:
            m=m//i
            if m==1:
                s=1
            if i in t.keys():
                t[i]+=1
            else:
                t[i]=1
            break
out=1
for tk in t.keys():
    out *= combi(t[tk]+n-1, n-1)
print(out%(1000000007))

Submission status: Runtime Error

Solution code:
N, M = [int(i) for i in input().split(' ')]
mod = pow(10, 9) + 7
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

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

NNN = 10**4
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

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

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

xxs = prime_decomposition(M)

result = 1
for xx in xxs:
    result = mul(result, cmb(xx+N-1,xx,mod))
print(result)

Submission status: Runtime Error

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

import sys
sys.setrecursionlimit(10**6)

MOD = 10**9 + 7
F = [M]
for x in range(2, int(sqrt(M))+1):
    if M % x == 0:
        F.append(x)
        if x != M // x:
            F.append(M // x)
F.sort(reverse=1)
L = len(F)
FF = [1]*(L+1)
fact = [1]*100
rfact = [1]*100
for i in range(L):
    FF[i+1] = FF[i] * (N - i) % MOD
for i in range(99):
    fact[i+1] = r = fact[i] * (i+1)
    rfact[i+1] = pow(r, MOD-2, MOD)
memo = {}
def dfs(i, rest, k):
    key = (i, rest, k)
    if i == L:
        if rest > 1:
            return 0
        return FF[k]
    if key in memo:
        return memo[key]
    f = F[i]
    r = dfs(i+1, rest, k)
    c = 0
    while rest % f == 0:
        rest //= f
        c += 1
        r = (r + dfs(i+1, rest, k+c) * rfact[c]) % MOD
    memo[key] = r
    return r
print(dfs(0, M, 0))

Submission status: Runtime Error

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

import sys
sys.setrecursionlimit(10**6)

MOD = 10**9 + 7
F = [M]
for x in range(2, int(sqrt(M))+1):
    if M % x == 0:
        F.append(x)
        F.append(M // x)
F.sort(reverse=1)
L = len(F)
FF = [1]*(L+1)
fact = [1]*100
rfact = [1]*100
for i in range(L):
    FF[i+1] = FF[i] * (N - i) % MOD
for i in range(99):
    fact[i+1] = r = fact[i] * (i+1)
    rfact[i+1] = pow(r, MOD-2, MOD)
memo = {}
def dfs(i, rest, k):
    key = (i, rest, k)
    if i == L:
        if rest > 1:
            return 0
        return FF[k]
    if key in memo:
        return memo[key]
    f = F[i]
    r = dfs(i+1, rest, k)
    c = 0
    while rest % f == 0:
        rest //= f
        c += 1
        r = (r + dfs(i+1, rest, k+c) * rfact[c]) % MOD
    memo[key] = r
    return r
print(dfs(0, M, 0))

Submission status: Runtime Error

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

MOD = 10**9 + 7
F = [M]
for x in range(2, int(sqrt(M))+1):
    if M % x == 0:
        F.append(x)
        F.append(M // x)
F.sort(reverse=1)
L = len(F)
FF = [1]*(L+1)
fact = [1]*41
rfact = [1]*41
for i in range(L):
    FF[i+1] = FF[i] * (N - i) % MOD
for i in range(40):
    fact[i+1] = r = fact[i] * (i+1)
    rfact[i+1] = pow(r, MOD-2, MOD)
memo = {}
def dfs(i, rest, k):
    key = (i, rest, k)
    if i == L:
        if rest > 1:
            return 0
        return FF[k]
    if key in memo:
        return memo[key]
    f = F[i]
    r = dfs(i+1, rest, k)
    c = 0
    while rest % f == 0:
        rest //= f
        c += 1
        r = (r + dfs(i+1, rest, k+c) * rfact[c]) % MOD
    memo[key] = r
    return r
print(dfs(0, M, 0))

Submission status: Runtime Error

Solution code:
from collections import defaultdict


def eratosthenes_generator():
    yield 2
    n = 3
    h = {}
    while True:
        m = n
        if n in h:
            b = h[n]
            m += 2 * b
            while m in h:
                m += 2 * b
            h[m] = b
            del h[n]
        else:
            m += 2 * n
            while m in h:
                m += 2 * n
            h[m] = n
            yield n
        n += 2


def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(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


def prime_factorize(n):
    f = defaultdict(lambda: 0)
    k = n
    for p in eratosthenes_generator():
        while True:
            d, m = divmod(k, p)
            if m == 0:
                f[p] += 1
                k = d
            else:
                break
        if k == 1:
            break
    return f


MOD = 1000000007
n, m = map(int, input().split())
pf = prime_factorize(m)
mx = max(pf.values())
f, r = prepare(n + mx, 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 math
N,M=map(int,input().split())
def primecheck(K):
    A=int(math.sqrt(K))+1
    for i in range(2,A+1):
        if K%i==0:
            return i
    return 1
D=dict()
while(True):
    X=int(math.sqrt(M))+1
    for i in range(2,X+1):
        if M%i==0:
            while(True):
                if i in D:
                    D[i]+=1
                else:
                    D[i]=1
                M=M//i
                if M%i!=0:
                    break
    if M==1:
        break
    j=primecheck(M)
    if j==1:
        D[M]=1
        break
    else:
        if j in D:
            D[j]=1
        else:
            D[j]+=1
P=10**9+7
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
def inv(x):
    return egcd(x,P)[0]
Y=3*N
Fact=[0 for i in range(Y+1)]
Finv=[0 for i in range(Y+1)]
Fact[0]=1
Finv[0]=1
for i in range(Y):
    Fact[i+1]=(Fact[i]*(i+1))%P
    Finv[i+1]=inv(Fact[i+1])%P
def C(n,k):
    return (Fact[n]*(Finv[k]*Finv[n-k])%P)%P
ans=1
for p in D:
    e=D[p]
    ans=ans*C(e+N-1,N-1)
    ans=ans%P
print(ans)