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:
from collections import Counter
from math import sqrt
n,m = (int(i) for i in input().split())
if n==1: ans = 1
else:
	m2,k,x,mod,ans = m,2,[],10**9+7,1
	while k**2<=m2:
		for i in range(k,int(sqrt(m2))+1):
			if m2%i==0:
				x.append(i)
				k,m2 = i,m2//i
				break
			elif i==int(sqrt(m2)): k = i+1
	x.append(m2)
	c,d = Counter(x).most_common(),[]
	for i,j in c: d.append(j)
	n2 = max(d)+n-1
	fn,fk = [1]*(n2),[1]*(n2)
	for i in range(n2-1): fn[i+1] = (fn[i]*(i+2))%mod
	def power(n,k):
		if k==1: return n
		elif k%2==0: return power((n**2)%mod,k//2)
		else: return (n*power(n,k-1))%mod
	def comb(n,k):
		if n==0 or k==0 or n==k: return 1
		else: return (((fn[n-1]*fk[n-k-1])%mod)*fk[k-1])%mod
	fk[-1] = power(fn[-1],mod-2)
	for i in range(2,n2+1): fk[-i] = (fk[-i+1]*(n2+2-i))%mod
	for i in d: ans = (ans*comb(i+n-1,i))%mod
print(ans)

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)


fac = [1, 1]
inv = [1, 1]
finv = [1, 1]
for i in range(2, n+max(b)+3):
    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%mod)

Submission status: Wrong Answer

Solution code:
import math
from collections import defaultdict

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

A = defaultdict(int)
p = 10 ** 9 + 7

if m == 1:
    print(1)

def fact(n, p=10**9 + 7):
    f = [1]
    for i in range(1, n+1):
        f.append(f[-1]*i%p)
    return f

def invfact(n, f, p=10**9 + 7):
    inv = [pow(f[n], p-2, p)]
    for i in range(n, 0, -1):
        inv.append(inv[-1]*i%p)
    return inv[::-1]

f = fact(30+10**5)
invf = invfact(30+10**5, f)

def comb(a, b):
    return f[a] * invf[b] * invf[a-b] % p

i = 2
rt = math.sqrt(m) + 1

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

if not A:
    print(n)
    exit()

n -= 1
ans = 1

for v in A.values():
    ans *= comb(v+n, n)
    ans %= p

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
from math import sqrt
n,m = (int(i) for i in input().split())
if n==1: ans = 1
else:
	m2,k,x,mod,ans = m,2,[],10**9+7,1
	while k**2<=m2:
		for i in range(k,int(sqrt(m2))+1):
			if m2%i==0:
				x.append(i)
				k,m2 = i,m2//i
				break
	x.append(m2)
	c,d = Counter(x).most_common(),[]
	for i,j in c: d.append(j)
	n2 = max(d)+n-1
	fn,fk = [1]*(n2),[1]*(n2)
	for i in range(n2-1): fn[i+1] = (fn[i]*(i+2))%mod
	def power(n,k):
		if k==1: return n
		elif k%2==0: return power((n**2)%mod,k//2)
		else: return (n*power(n,k-1))%mod
	def comb(n,k):
		if n==0 or k==0 or n==k: return 1
		else: return (((fn[n-1]*fk[n-k-1])%mod)*fk[k-1])%mod
	fk[-1] = power(fn[-1],mod-2)
	for i in range(2,n2+1): fk[-i] = (fk[-i+1]*(n2+2-i))%mod
	for i in d: ans = (ans*comb(i+n-1,i))%mod
print(ans)

Submission status: Wrong Answer

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

m2 = int(math.sqrt(m))

n_so = {}

for i in range(2,m2+2):
    t = 0
    while m%i == 0:
        m = int(m/i)
        t += 1
    if t > 0:
        n_so[i] = t
        if m == 1:
            break
ans = 1
su = n_so.values()

for i in su:
    ans = ans * (math.factorial(n-1+i)/(math.factorial(i)*math.factorial(n-1))) % (10**9+7)

print(int(ans))

Submission status: Wrong Answer

Solution code:
import math
from collections import defaultdict

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

A = defaultdict(int)
p = 10 ** 9 + 7

if m == 1:
    print(1)

def fact(n, p=10**9 + 7):
    f = [1]
    for i in range(1, n+1):
        f.append(f[-1]*i%p)
    return f

def invfact(n, f, p=10**9 + 7):
    inv = [pow(f[n], p-2, p)]
    for i in range(n, 0, -1):
        inv.append(inv[-1]*i%p)
    return inv[::-1]

f = fact(30+10**5)
invf = invfact(30+10**5, f)

def comb(a, b):
    return f[a] * invf[b] * invf[a-b] % p

i = 2
rt = math.sqrt(m) + 1

while m != 1 and (A or i <= rt):
    while m % i == 0:
        m //= i
        A[i] += 1
    i += 1

if not A:
    print(n)
    exit()

n -= 1
ans = 1

for v in A.values():
    ans *= comb(v+n, n)
    ans %= p

print(ans)

Submission status: Wrong Answer

Solution code:
import math
from collections import defaultdict

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

A = defaultdict(int)
p = 10 ** 9 + 7

if m == 1:
    print(1)

def fact(n, p=10**9 + 7):
    f = [1]
    for i in range(1, n+1):
        f.append(f[-1]*i%p)
    return f

def invfact(n, f, p=10**9 + 7):
    inv = [pow(f[n], p-2, p)]
    for i in range(n, 0, -1):
        inv.append(inv[-1]*i%p)
    return inv[::-1]

f = fact(30+10**5)
invf = invfact(30+10**5, f)

def comb(a, b):
    return f[a] * invf[b] * invf[a-b] % p

i = 2
rt = math.sqrt(m) + 1

while m != 1 and (A or i <= math.sqrt(m)):
    while m % i == 0:
        m //= i
        A[i] += 1
    i += 1

if not A:
    print(n)
    exit()

n -= 1
ans = 1

for v in A.values():
    ans *= comb(v+n, n)
    ans %= p

print(ans)

Submission status: Wrong Answer

Solution code:
import math
from collections import defaultdict

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

A = defaultdict(int)
p = 10 ** 9 + 7

if n == 1:
    print(1)

def fact(n, p=10**9 + 7):
    f = [1]
    for i in range(1, n+1):
        f.append(f[-1]*i%p)
    return f

def invfact(n, f, p=10**9 + 7):
    inv = [pow(f[n], p-2, p)]
    for i in range(n, 0, -1):
        inv.append(inv[-1]*i%p)
    return inv[::-1]

f = fact(30+10**5)
invf = invfact(30+10**5, f)

def comb(a, b):
    return f[a] * invf[b] * invf[a-b] % p

i = 2
rt = math.sqrt(m) + 1

while m != 1 and (A or i <= rt):
    while m % i == 0:
        m //= i
        A[i] += 1
    i += 1

if not A:
    print(n)
    exit()

n -= 1
ans = 1

for v in A.values():
    ans *= comb(v+n, n)
    ans %= p

print(ans)

Submission status: Wrong Answer

Solution code:
import math
n,m = map(int, input().split())
ls = []
c = 0
d = 1

for i in range(2,m) :
   if m == 1 :
      break
   while m%i == 0 :
      c += 1
      m = m/i

   ls.append(c)
   c = 0

for j in range(len(ls)) :
   d = int( d * math.factorial(ls[j]+n-1)/math.factorial(n-1)/math.factorial(ls[j]) )

print(d%(10**9+7))

Submission status: Wrong Answer

Solution code:
import math

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

def factorized(M):
    maxd = int(math.sqrt(M))
    d = 2
    f = []
    while d <= M and d <= maxd:
        count = 0
        while M % d == 0:
            M //= d
            count += 1
        if count > 0:
            f.append(count)
        d += 1
    return f

def tetra(n, m):
    x = 1
    for y in range(1, n):
        x = x * (m + y - 1) // y
    return x

x = 1
for f in factorized(M):
    x *= tetra(N, f + 1)
    x %= 10 ** 9 + 7

print(x)