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: Wrong Answer

Solution code:
def comb(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])

    return result;

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

yaku = []
flg = 1
while flg == 1:
    for i in range(2,int(m**0.5)+2):
        if m % i == 0:
            m = int(m / i)
            yaku.append(i)
            break
    else:
        yaku.append(m)
        flg = 0
yakuset = set(yaku)
num = []
for i in yakuset:
    num.append(yaku.count(i))

mod = int(10e8 + 7)
counter = 1
for i in num:
    rez = int(comb(n-1+i,i)) % mod
    counter = (counter*rez) % mod
print(counter)

Submission status: Wrong Answer

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

mod = 10 ** 9 + 7

b = []

c = int(math.sqrt(m))
for i in range(2, c+3):
    count = 0
    while m % i == 0:
        count += 1
        m = m // i
    b.append(count)


#combination---
#nとmは適宜変える

fac = [1, 1]
inv = [1, 1]
finv = [1, 1]
for i in range(2, n+max(b)):
    fac.append(fac[i-1] * i % mod)
    inv.append(mod - inv[mod%i] * (mod//i) % mod)
    finv.append(finv[i-1] * inv[i] % mod)

def nck(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

#-----
ans = 1
for i in b:
    ans *= nck(n-1+i, n-1)
    ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin

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


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

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

from collections import Counter

n,m = li()

MOD = 10**9+7

# 二項係数の準備
inv = inv_mod(n,MOD)
fac = fact(n,MOD)
facInv = fact_inv(n,inv,MOD)


# Mの素因数リストを作る

def cd(n:int):
    m = 2
    cds = [n]
    while m*m <= n:
        if n%m == 0:
            cds.append(m)
            cds.append(n//m)
            
        m += 1

    return sorted(cds)
    
cds = cd(m)

memo = []

def dfs(m: int, cds: list, res:int,st:list):
    if res == 1:
        memo.append(st)
        
    else:
        for cdi in cds:
            if cdi > st[-1]:
                pass
            else:
                if res%cdi == 0:
                    dfs(m,cds,res//cdi,st+[cdi])
                

# 辞書順にmを作れるオリジナルなセットを作る
memo = []
for cdi in cds:
    dfs(m,cds,m//cdi,[cdi])

ans = 0
for memoi in memo:
    cnt = Counter(memoi)
    cnt_v = list(cnt.values())
    temp = fac[n]
    if len(memoi) <= n:
        for cnt_vi in cnt_v:
            temp = (temp*facInv[cnt_vi]) % MOD
        temp = (temp*facInv[n-len(memoi)]) % MOD
    
    ans = (ans+temp) % MOD
        
        
print(ans%MOD)

Submission status: Wrong Answer

Solution code:
from collections import Counter
Q = 10**9+7
def primes(n):
    primfac = []
    d = 2
    while d*d <= n:
        while (n % d) == 0:
            primfac.append(d)  # supposing you want multiple factors repeated
            n //= d
        d += 1
    if n > 1:
       primfac.append(n)
    return primfac

def factorial(n):
    P = 1
    for i in range(1,n+1):
        P *= i
    return P

def combination(a,b):
    return int( (factorial(a)/factorial(b))/factorial(a-b))%Q
N, M = map( int, input().split())
C = Counter( primes(M))
ans = 1
print(C)
if N == 1:
    print(1)
else:
    for x in C:
        ans = (ans * combination(C[x]+N-1,N-1))%Q
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin

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


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

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

from collections import Counter

n,m = li()

MOD = 10**9+7

# 二項係数の準備
inv = inv_mod(n,MOD)
fac = fact(n,MOD)
facInv = fact_inv(n,inv,MOD)


# Mの素因数リストを作る

def cd(n:int):
    m = 2
    cds = [n]
    while m*m <= n:
        if n%m == 0:
            cds.append(m)
            cds.append(n//m)
            
        m += 1

    return sorted(cds)
    
cds = cd(m)

memo = []

def dfs(m: int, cds: list, res:int,st:list, memo:list):
    if res == 1:
        memo.append(st)
        
    else:
        for cdi in cds:
            if cdi > st[-1]:
                pass
            else:
                if res%cdi == 0:
                    dfs(m,cds,res//cdi,st+[cdi],memo)
                

# 辞書順にmを作れるオリジナルなセットを作る
memo = []
for cdi in cds:
    dfs(m,cds,m//cdi,[cdi],memo)

ans = 0
for memoi in memo:
    cnt = Counter(memoi)
    cnt_v = list(cnt.values())
    temp = fac[n]
    if len(memoi) <= n:
        for cnt_vi in cnt_v:
            temp = (temp*facInv[cnt_vi]) % MOD
        temp = (temp*facInv[n-len(memoi)]) % MOD
    
    ans += temp
        
        
print(ans%MOD)

Submission status: Wrong Answer

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

mod = 10 ** 9 + 7

b = []

c = int(math.sqrt(m))
for i in range(2, c+2):
    count = 0
    while m % i == 0:
        count += 1
        m = m // i
    b.append(count)


#combination---
#nとmは適宜変える

fac = [1, 1]
inv = [1, 1]
finv = [1, 1]
for i in range(2, n+max(b)):
    fac.append(fac[i-1] * i % mod)
    inv.append(mod - inv[mod%i] * (mod//i) % mod)
    finv.append(finv[i-1] * inv[i] % mod)

def nck(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

#-----
ans = 1
for i in b:
    ans *= nck(n-1+i, i)
    ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
import math

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

mo=10**9+7

yak=[0 for i in range(10**5)]


for i in range(2,int(m**0.5)+2):

    while m%i==0 :
            m=m//i
            yak[i]+=1

#print(y)  
#print(yak[:10])

co=1

for i in range(10**5):
    if yak[i]>0 :
        nn=n+yak[i]-1
        r=yak[i]
        t=(math.factorial(nn) // (math.factorial(nn - r) * math.factorial(r)))%mo
        co=(co*t)%mo

print(co)

Submission status: Wrong Answer

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

yaku = []
flg = 1
while flg == 1:
    for i in range(2,int(m**0.5)+2):
        if m % i == 0:
            m = int(m / i)
            yaku.append(i)
            break
    else:
        yaku.append(m)
        flg = 0
yakuset = set(yaku)
num = []
for i in yakuset:
    num.append(yaku.count(i))

mod = int(10e8 + 7)
counter = 1
for i in num:
    rez = 1
    for j in range(i):
        rez *= n-1+i-j
    for j in range(i):
        rez = rez//(j+1)
    counter = (counter*rez) % mod
print(counter)