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
def find(M):
    fact=[]
    while M>1:
        in1=len(fact)
        for i in range(2,int(M**0.5)+1):
            if M%i==0:
                fact+=[i]
                M=M//i
                break
        in2=len(fact)
        if in1==in2:
            break
    fact+=[M]
    return fact
N,M=list(map(int,input().strip().split(' ')))
dic=Counter(find(M))
fact=[1]
temp=1
MOD=10**9+7
for i in range(1,10**6):
    temp*=i
    temp%=MOD
    fact+=[temp]


ans=1
for x in dic:
    y=dic[x]
    #bino(N+y-1,y)
    up=fact[N+y-1]
    down=(fact[y]*fact[N-1])%MOD
    ans*=(up*pow(down,MOD-2,MOD))%MOD
    ans%=MOD
print(ans)

Submission status: Wrong Answer

Solution code:
from operator import mul
from functools import reduce
from collections import Counter
MOD = 10 ** 9 + 7
N, M = map(int, input().split())

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(lambda x, y : x * y % MOD, range(n, n - r, -1))
    under = reduce(lambda x, y : x * y % MOD, range(1,r + 1))
    return over * pow(under, MOD - 2, MOD)

F = []
def fct(m):
    for i in range(2, int(m**0.5)+1):
        if m % i == 0:
            return i, m//i
    return m, None

i, m = fct(M)
while m:
    F.append(i)
    i, m = fct(m)
F.append(i)

C = Counter(F)

cum = 1
for v in C.values():
    cum *= cmb(N+v-1, v)
    cum %= MOD

print(cum)

Submission status: Wrong Answer

Solution code:
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    elif n<r: return 0
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under
md=10**9+7

n,m=map(int,input().split())
s=[[0,0]]
if m==1:
  s.append([1,1])
for i in range(2,int(m**(0.5)+1)):
  k=0
  frag = 0
  if m%i!=0:
    frag = 1
  while m%i==0:
    m=int(m/i)
    k=k+1
  if frag == 0:
    s.append([i,k])
if m!=1:
  s.append([m,1])
q = [0]*(len(s)-1)
for i in range(1,len(s)):
  q[i-1] = s[i][1]

t = 1
for i in range(len(q)):
  c = cmb(n-1+q[i],q[i])
  t = t*(c%md)
  
print(t%md)

Submission status: Wrong Answer

Solution code:
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under
md=10**9+7

n,m=map(int,input().split())
s=[[0,0]]
if m==1:
  s.append([1,1])
for i in range(2,int(m**(0.5)+1)):
  k=0
  frag = 0
  if m%i!=0:
    frag = 1
  while m%i==0:
    m=int(m/i)
    k=k+1
  if frag == 0:
    s.append([i,k])
if m!=1:
  s.append([m,1])
q = [0]*(len(s)-1)
for i in range(1,len(s)):
  q[i-1] = s[i][1]

t = 1
for i in range(len(q)):
  c = cmb(n-1+q[i],q[i])
  t = t*(c%md)
  
print(t%md)

Submission status: Wrong Answer

Solution code:
import math
def cmb(n, r):
  if n < r : return 0
  else : return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
md=10**9+7

n,m=map(int,input().split())
s=[[0,0]]
if m==1:
  s.append([1,1])
for i in range(2,int(m**(0.5)+1)):
  k=0
  frag = 0
  if m%i!=0:
    frag = 1
  while m%i==0:
    m=int(m/i)
    k=k+1
  if frag == 0:
    s.append([i,k])
if m!=1:
  s.append([m,1])
q = [0]*(len(s)-1)
for i in range(1,len(s)):
  q[i-1] = s[i][1]

t = 1
for i in range(len(q)):
  c = cmb(n-1+q[i],q[i])
  t = t*(c%md)
  
print(t%md)

Submission status: Wrong Answer

Solution code:
import math
def factorize(m):
    fct = []
    b = 2
    while b * b <= m:
        cnt = 0
        while m % b == 0:
            m //= b
            cnt += 1
        if cnt > 0:
            fct.append(cnt)
        b += 1 
    return fct

def comb(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    else:
        return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))

N, M = map(int, input().split())
ans = 1
M_fct = factorize(M)

for mf in M_fct:
    #mf[1]個をN通りに分ける→comb(mf[1]+N-1,mf[1])
    ans *= comb(N + mf - 1, mf)
    ans %= 10**9+7
print(ans)

Submission status: Wrong Answer

Solution code:
import math
def factorize(m):
    fct = []
    tmp = int(math.sqrt(m))+1
    for i in range(2,tmp):
        if m % i == 0:
            cnt = 0
            while m % i == 0:
                cnt += 1
                m //= i
            fct.append([i, cnt])
    if m != 1:
        fct.append([m, 1])
    if fct == []:
        fct.append([m,1])
    return fct

def comb(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    else:
        return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))

N, M = map(int, input().split())
ans = 1
M_fct = factorize(M)

for mf in M_fct:
    #mf[1]個をN通りに分ける→comb(mf[1]+N-1,mf[1])
    ans *= comb(N + mf[1] - 1, mf[1])
print(ans% (10 ** 9 + 7))

Submission status: Wrong Answer

Solution code:
import math
def factorize(m):
    fct = []
    for i in range(2,int(-(-m**0.5//1))+1):
        if m % i == 0:
            cnt = 0
            while m % i == 0:
                cnt += 1
                m //= i
            fct.append([i, cnt])
    if m != 1:
        fct.append([m, 1])
    if fct == []:
        fct.append([m,1])
    return fct

def comb(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    else:
        return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))

N, M = map(int, input().split())
ans = 1
M_fct = factorize(M)

for mf in M_fct:
    #mf[1]個をN通りに分ける→comb(mf[1]+N-1,mf[1])
    ans *= comb(N+mf[1]-1,mf[1])
print(ans%(10**9+7))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
s=[[0,0]]
if m==1:
  s.append([1,1])
for i in range(2,int(m**(0.5)+1)):
  k=0
  frag = 0
  if m%i!=0:
    frag = 1
  while m%i==0:
    m=int(m/i)
    k=k+1
  if frag == 0:
    s.append([i,k])
if m!=1:
  s.append([m,1])
q = [0]*(len(s)-1)
for i in range(1,len(s)):
  q[i-1] = s[i][1]


def kai(m,n):
  if n == 0:
    return(1)
  else:
    t = m
    for i in range(m+1,n+1):
      t = t*i
    return(t)

t = 1
for i in range(len(q)):
  d = max(n-1,q[i])
  c = int(kai(d+1,n-1+q[i])/kai(1,n-1+q[i]-d))
  t = (t%((10**9)+7))*(c%((10**9)+7))
  
print(t%((10**9)+7))

Submission status: Wrong Answer

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

def factoring(k): #kを因数分解し、素因数とその個数を辞書に入れて返す。
    dic = dict()
    n = int(math.sqrt(k))+2
    for i in range(2, n):
        count = 0
        while k%i == 0:
            count += 1
            k = k//i
        if count != 0:
            dic[i] = count
    return dic

def conbination(n, r): #nCrを求める
    # nCr = n! //(r! * (n-r)!)
    import math
    return (math.factorial(n) //(math.factorial(r) * math.factorial(n-r)))%MOD
dic = factoring(M)
ans = 1
for i in dic:
    ans = (ans * conbination(dic[i]+N-1, dic[i]))%MOD
print (ans)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def divisions(n):
    sq = int(math.sqrt(n)+1)
    ss = 30030
    a = [None] * (ss)
    a[0] = 1
    t = 1
    for i in range(2,ss):
        if not a[i] is None:
            continue
        if t * i > ss:
            break
        t *= i
        for j in range(i*2,ss,i):
            a[j] = 1
    a = [i for i in range(t) if a[i] is None]
    d = collections.defaultdict(int)
    for i in a[1:]:
        while n % i == 0:
            n //= i
            d[i] += 1

    for j in range(1,sq//t+2):
        if t*j > n:
            break
        for ii in a:
            i = t*j+ii
            while n % i == 0:
                n //= i
                d[i] += 1

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

    return d

def inv(x):
    return pow(x, mod - 2, mod)

cms = 10**5 + 100
cm = [0] * cms

def comb_init():
    cm[0] = 1
    for i in range(1, cms):
        cm[i] = cm[i-1] * i % mod

def comb(a, b):
    return (cm[a] * inv(cm[a-b]) % mod) * inv(cm[b]) % mod

def main():
    n,m = LI()

    comb_init()
    d = divisions(m)
    r = 1
    for v in d.values():
        a,b = n,v
        if a < b:
            a,b = b,a
        r *= comb(a+b-1,b)
        r %= mod

    return r


print(main())

Submission status: Wrong Answer

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

MAX = 2*10**5+1
MOD = 10**9+7
fact = [0 for i in range(MAX)]
inv = [0 for i in range(MAX)]
invfact = [0 for i in range(MAX)]

def comb_build(n):
  fact[0] = inv[0] = invfact[0] = 1
  fact[1] = inv[1] = invfact[1] = 1
  for i in range(2, n):
    fact[i] = fact[i-1]*i%MOD
    inv[i] = inv[MOD%i]*(MOD-MOD//i)%MOD
    invfact[i] = invfact[i-1]*inv[i]%MOD

def nCk(n, k):
  if n<k or n<0 or k<0:
    return 0
  return (((fact[n]*invfact[k])%MOD)*invfact[n-k])%MOD

def prime_factor(n):
  from collections import defaultdict
  ret = defaultdict(int)
  for i in range(2, int(n**(1/2))+10):
    while n%i==0:
      ret[i] += 1
      n //= i
  return ret

comb_build(MAX)
ans = 1
for e in prime_factor(m).values():
  ans *= nCk(e+n-1, e)%MOD
print(ans%MOD)

Submission status: Wrong Answer

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

MAX = 2*10**5+1
MOD = 10**9+7
fact = [0 for i in range(MAX)]
inv = [0 for i in range(MAX)]
invfact = [0 for i in range(MAX)]

def comb_build(n):
  fact[0] = inv[0] = invfact[0] = 1
  fact[1] = inv[1] = invfact[1] = 1
  for i in range(2, n):
    fact[i] = fact[i-1]*i%MOD
    inv[i] = inv[MOD%i]*(MOD-MOD//i)%MOD
    invfact[i] = invfact[i-1]*inv[i]%MOD

def nCk(n, k):
  if n<k or n<0 or k<0:
    return 0
  return (((fact[n]*invfact[k])%MOD)*invfact[n-k])%MOD

def prime_factor(n):
  from collections import defaultdict
  ret = defaultdict(int)
  for i in range(2, int(n**(1/2))+1):
    while n%i==0:
      ret[i] += 1
      n //= i
  return ret

comb_build(MAX)
ans = 1
for e in prime_factor(m).values():
  ans *= nCk(e+n-1, e)%MOD
print(ans%MOD)

Submission status: Wrong Answer

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

def sieve_of_eratosthenes(n):
    pl = [i for i in range(2, n + 1)] 
    i=0
    p = pl[0]
    while p**2<=n:
        pl = [pl[j] for j in range(len(pl)) if pl[j]%p!=0 or j<=i]
        i+=1
        p=pl[i]
    return pl

pl = sieve_of_eratosthenes(100000)

p_list = []
pow_list = []
for p in pl:
    if M%p==0:
        p_list.append(p)
        count=1
        pp = p*p
        for j in range(1,30):
            if M%pp==0:
                count+=1
            else:
                break
            pp*=p
        pow_list.append(count)

if len(pow_list)==0:
    pow_list.append(1)

comb = [N]
mod = 10**9 + 7
for i in range(2,32):
    temp = comb[i-2]*(N+i-1)
    temp = temp//i
    comb.append(temp)

ans=1
for c in pow_list:
    ans=(comb[c-1]*ans)%mod

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

prime = defaultdict(int)
m = M
for i in range(2, 10 ** 5):
    while m % i == 0 and m > 1:
        prime[i] += 1
        m //= i

MOD = 10 ** 9 + 7

def comb(n, k):
    a = 1
    for i in range(1, k + 1):
        a *= n - i + 1
        a %= MOD
        
        a *= pow(i, MOD - 2, MOD)
        a %= MOD
        
    return a

ans = 1
for _, t in prime.items():
    ans *= comb(N - 1 + t, t)
    ans %= MOD
    
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

prime = defaultdict(int)
m = M
for i in range(2, 10 ** 5):
    while m % i == 0:
        prime[i] += 1
        m //= i

MOD = 10 ** 9 + 7

def comb(n, k):
    a = 1
    for i in range(1, k + 1):
        a *= n - i + 1
        a %= MOD
        
        a *= pow(i, MOD - 2, MOD)
        a %= MOD
        
    return a

ans = 1
for _, t in prime.items():
    ans *= comb(N - 1 + t, t)
    ans %= MOD
    
print(ans)

Submission status: Wrong Answer

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

from math import factorial
from collections import Counter

def soinsuu(n):
    list_=[]
    while(n!=1):
        for i in range(2,int(n**0.5)+1):
            if n%i==0:
                list_.append(i)
                n=n//i
                break
        else:
            list_.append(n)
            n=1
    return sorted(list_)

def product(a):
    pro=1
    for b in a:
        pro=pro*b%mod
    return pro

#n!,nPr,nCrの高速計算
def n_func(n,mod=10**9+7):
    ans=1
    for i in range(1,n+1):
        ans=(ans*i)%mod
    return ans
def inv_n(n,mod=10**9+7):
    return pow(n,mod-2,mod)
def nPr(n,r,mod=10**9+7):
    ans=n_func(n-r,mod)
    ans=inv_n(ans,mod)
    return ans*n_func(n,mod)%mod

def dp(cur,init,seq,lest,num):
    if cur==N:
        if lest==0:
            cnt=sorted(list(Counter(seq).values()),reverse=True)
            #print(cnt)
            bunbo=product(map(factorial,cnt[1:]))
            memo[num]=(memo[num]+nPr(sum(cnt),sum(cnt[1:]),mod)//bunbo)%mod #ここがおかしい
    elif lest==0:
        dp(N,init,seq+[0]*(N-cur),0,num)
    else:
        for i in range(1,lest+1):##
            if cur==0:
                dp(cur+1,init,seq+[i],lest-i,num)
            elif i<=seq[-1]:
                dp(cur+1,init,seq+[i],lest-i,num)

p=list(Counter(soinsuu(M)).values())
memo=[0]*len(p)

#print(p)

for i in range(len(p)):
    dp(0,p[i],[],p[i],i)
#print(memo)
print(product(memo))
#print(p)

Submission status: Wrong Answer

Solution code:
import math

x = 10**9 + 7

def primefact(M, S={}):
    if M == 1 and S == {}:
        return {1:1}
    while M > 1:
        for m in range(2,M+2):
            if M%m == 0 and m in S:
                S[m] += 1
                M = M//m
                break
            elif M%m == 0:
                S[m] = 1
                M = M//m
                break
        else:
            break
            return {M:1}
    else:
        return S
    
def H(n,k):
    A = list(range(n,n+k))
    S = 1
    for a in A:
        S = S*a
    return (S//k)%x

N, M = map(int, input().split())
P = primefact(M)
ans = 1

for p in P:
    ans = (ans * H(N,P[p]))
    
print(ans)

Submission status: Wrong Answer

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


def factorization(n):  # => {p:count,...}
    fac = {}
    for i in range(2, int(n ** .5) + 1):
        count = 0
        while n % i == 0:
            n //= i
            count += 1
        if count > 0:
            fac[i] = count
    if n > 1:
        fac[n] = 1
    return fac


def C(n, r, mod):
    r = min(n - r, r)
    if r == 0:
        return 1
    over = list(range(n, n - r, -1))
    for k in range(2, r + 1):
        for i, o in enumerate(over):
            if o % k == 0:
                over[i] //= k
                break
    ret = 1
    for o in over:
        ret *= o
        ret %= mod
    return ret


ans = 1
for c in factorization(m).values():
    ans *= C(c + n - 1, c, mod)
    ans %= mod
print(ans)

Submission status: Wrong Answer

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


def factorization(n):  # => {p:count,...}
    fac = {}
    count = 0
    while n % 2 == 0:
        n //= 2
        count += 1
    if count > 0:
        fac[2] = count
    for i in range(3, int(n ** .5) + 100, 2):
        count = 0
        while n % i == 0:
            n //= i
            count += 1
        if count > 0:
            fac[i] = count
    if n > 1:
        fac[n] = 1
    return fac


def C(n, r, mod):
    r = min(n - r, r)
    if r == 0:
        return 1
    over = list(range(n, n - r, -1))
    for k in range(2, r + 1):
        for i, o in enumerate(over):
            if o % k == 0:
                over[i] //= k
                break
    ret = 1
    for o in over:
        ret *= o
        ret %= mod
    return ret


ans = 1
for c in factorization(m).values():
    ans *= C(c + n - 1, c, mod)
    ans %= mod
print(ans)

Submission status: Wrong Answer

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


def factorization(n):  # => {p:count,...}
    fac = {}
    count = 0
    while n % 2 == 0:
        n //= 2
        count += 1
    if count > 0:
        fac[2] = count
    for i in range(3, int(n ** .5) + 2, 2):
        count = 0
        while n % i == 0:
            n //= i
            count += 1
        if count > 0:
            fac[i] = count
    if n > 1:
        fac[n] = 1
    return fac


def C(n, r, mod):
    r = min(n - r, r)
    if r == 0:
        return 1
    over = list(range(n, n - r, -1))
    for k in range(2, r + 1):
        for i, o in enumerate(over):
            if o % k == 0:
                over[i] //= k
                break
    ret = 1
    for o in over:
        ret *= o
        ret %= mod
    return ret


ans = 1
for c in factorization(m).values():
    ans *= C(c + n - 1, c, mod)
    ans %= mod
print(ans)

Submission status: Wrong Answer

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


def factorization(n):  # => {p:count,...}
    fac = {}
    count = 0
    while n % 2 == 0:
        n //= 2
        count += 1
    if count > 0:
        fac[2] = count
    for i in range(3, int(n ** .5) + 1, 2):
        count = 0
        while n % i == 0:
            n //= i
            count += 1
        if count > 0:
            fac[i] = count
    if n > 1:
        fac[n] = 1
    return fac


def C(n, r, mod):
    r = min(n - r, r)
    if r == 0:
        return 1
    over = list(range(n, n - r, -1))
    for k in range(2, r + 1):
        for i, o in enumerate(over):
            if o % k == 0:
                over[i] //= k
                break
    ret = 1
    for o in over:
        ret *= o
        ret %= mod
    return ret


ans = 1
for c in factorization(m).values():
    ans *= C(c + n - 1, c, mod)
    ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import defaultdict



MOD = 10**9+7
FACTOR = []

def factrial(n):
  global FACTOR
  FACTOR = [1 for _ in range(n+1)]
  for i in range(1,n+1):
    FACTOR[i] = (FACTOR[i-1]*i) % MOD

def mul(a,b):
  return (a*b) % MOD

def power(a,b):
  ## 二分累乗法
  if   b==0   : return 1
  elif b==1   : return a % MOD
  elif b%2==0 : return power(a,b//2)**2 % MOD
  else        : return power(a,b//2)**2 * a % MOD

def div(a,b):
  ## MOD同士の割り算
  return mul(a,power(b,MOD-2))

## 素因数分解
def factoring(m):
  fact = defaultdict(lambda:0)
  idx = 2
  while m > idx:
    if m%idx==0:
      fact[idx] += 1
      m //= idx
    else:
      idx += 1
  fact[m] += 1
  ret = []
  for k in fact:
    ret.append(fact[k])
  return ret

def combi(a,b):
  if a<b:
    return 1
  else:
    return div(FACTOR[a], (FACTOR[b]*FACTOR[abs(a-b)])%MOD)


def main():
  N,M = map(int, input().split())
  if N == 1:
    print(1)
  else:
    fact = factoring(M)
    factrial(N+max(fact))
    ans = 1
    for f in fact:
      ans = (ans * combi(f+N-1,N-1)) % MOD
    print(ans)


if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import defaultdict



MOD = 10**9+7
FACTOR = []

def factrial(n):
  global FACTOR
  FACTOR = [1 for _ in range(n+1)]
  for i in range(1,n+1):
    FACTOR[i] = (FACTOR[i-1]*i) % MOD

def mul(a,b):
  return (a*b) % MOD

def power(a,b):
  ## 二分累乗法
  if   b==0   : return 1
  elif b==1   : return a % MOD
  elif b%2==0 : return power(a,b//2)**2 % MOD
  else        : return power(a,b//2)**2 * a % MOD

def div(a,b):
  ## MOD同士の割り算
  return mul(a,power(b,MOD-2))

## 素因数分解
def factoring(m):
  fact = defaultdict(lambda:0)
  idx = 2
  while m > idx:
    if m%idx==0:
      fact[idx] += 1
      m //= idx
    else:
      idx += 1
  fact[m] += 1
  ret = []
  for k in fact:
    ret.append(fact[k])
  return ret

def combi(a,b):
  if a<b:
    return 1
  else:
    return div(FACTOR[a], (FACTOR[b]*FACTOR[abs(a-b)])%MOD)


def main():
  N,M = map(int, input().split())
  fact = factoring(M)
  factrial(N+max(fact))
  ans = 1
  for f in fact:
    ans = (ans * combi(f+N-1,N-1)) % MOD
  print(ans)


if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import defaultdict


MOD = 10**9+7
FACT = [1 for _ in range(10**5+100)]
for i in range(1,10**5+100):
  FACT[i] = (FACT[i-1]*(i)) % MOD


def mul(a,b):
  return (a*b) % MOD

def power(a,b):
  ## 二分累乗法
  if   b==0   : return 1
  elif b==1   : return a % MOD
  elif b%2==0 : return power(a,b//2)**2 % MOD
  else        : return power(a,b//2)**2 * a % MOD

def div(a,b):
  ## MOD同士の割り算
  return mul(a,power(b,MOD-2))

def combi(a,b):
  return div(FACT[a]%MOD, (FACT[b]*FACT[abs(a-b)])%MOD)

def fact(m):
  ret = defaultdict(lambda:0)
  i = 2
  while m > i:
    if m%i == 0:
      ret[i] += 1
      m //= i
    else:
      i += 1
  ret[m] += 1
  return ret


def main():
  N,M = map(int, input().split())
  dct = fact(M)
  ans = 1
  for k in dct:
    ans = (ans * combi(dct[k]+N-1, N-1))%MOD
  print(max(ans,1))


if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import defaultdict


MOD = 10**9+7
FACT = [1 for _ in range(10**5+100)]
for i in range(1,10**5+100):
  FACT[i] = (FACT[i-1]*(i)) % MOD


def mul(a,b):
  return (a*b) % MOD

def power(a,b):
  ## 二分累乗法
  if   b==0   : return 1
  elif b==1   : return a % MOD
  elif b%2==0 : return power(a,b//2)**2 % MOD
  else        : return power(a,b//2)**2 * a % MOD

def div(a,b):
  ## MOD同士の割り算
  return mul(a,power(b,MOD-2))

def combi(a,b):
  return div(FACT[a]%MOD, (FACT[b]*FACT[abs(a-b)])%MOD)

def fact(m):
  ret = defaultdict(lambda:0)
  i = 2
  while m > i:
    if m%i == 0:
      ret[i] += 1
      m //= i
    else:
      i += 1
  ret[m] += 1
  return ret


def main():
  N,M = map(int, input().split())
  dct = fact(M)
  ans = 1
  for k in dct:
    ans = (ans * combi(dct[k]+N-1, N-1))%MOD
  print(ans)


if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import defaultdict


MOD = 10**9+7
FACT = [1 for _ in range(10**5+100)]
for i in range(1,10**5+100):
  FACT[i] = (FACT[i-1]*(i)) % MOD


def mul(a,b):
  return (a*b) % MOD

def power(a,b):
  ## 二分累乗法
  if   b==0   : return 1
  elif b==1   : return a % MOD
  elif b%2==0 : return power(a,b//2)**2 % MOD
  else        : return power(a,b//2)**2 * a % MOD

def div(a,b):
  ## MOD同士の割り算
  return mul(a,power(b,MOD-2))

def combi(a,b):
  return div(FACT[a]%MOD, (FACT[b]*FACT[a-b])%MOD)

def fact(m):
  ret = defaultdict(lambda:0)
  i = 2
  while m > i:
    if m%i == 0:
      ret[i] += 1
      m //= i
    else:
      i += 1
  ret[m] += 1
  return ret


def main():
  N,M = map(int, input().split())
  dct = fact(M)
  ans = 1
  for k in dct:
    ans = (ans * combi(dct[k]+N-1, N-1))%MOD
  print(ans)


if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import defaultdict


MOD = 10**9+7
FACT = [1 for _ in range(10**5*2)]
for i in range(1,10**5*2):
  FACT[i] = (FACT[i-1]*(i)) % MOD


def mul(a,b):
  return (a*b) % MOD

def power(a,b):
  ## 二分累乗法
  if   b==0   : return 1
  elif b==1   : return a % MOD
  elif b%2==0 : return power(a,b//2)**2 % MOD
  else        : return power(a,b//2)**2 * a % MOD

def div(a,b):
  ## MOD同士の割り算
  return mul(a,power(b,MOD-2))

def combi(a,b):
  return div(FACT[a]%MOD, (FACT[b]*FACT[a-b])%MOD)

def fact(m):
  ret = defaultdict(lambda:0)
  i = 2
  while m > i:
    if m%i == 0:
      ret[i] += 1
      m //= i
    else:
      i += 1
  ret[m] += 1
  return ret


def main():
  N,M = map(int, input().split())
  dct = fact(M)
  ans = 1
  for k in dct:
    ans = (ans * combi(dct[k]+N-1, N-1))%MOD
  print(ans)


if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import defaultdict


MOD = 10**9+7
FACT = [1 for _ in range(10**5*2)]
for i in range(1,10**5*2):
  FACT[i] = (FACT[i-1]*(i)) % MOD


def mul(a,b):
  return (a*b) % MOD

def power(a,b):
  ## 二分累乗法
  if   b==0   : return 1
  elif b==1   : return a % MOD
  elif b%2==0 : return power(a,b//2)**2 % MOD
  else        : return power(a,b//2)**2 * a % MOD

def div(a,b):
  ## MOD同士の割り算
  return mul(a,power(b,MOD-2))

def combi(a,b):
  print(a,b,a-b)
  return div(FACT[a]%MOD, (FACT[b]*FACT[a-b])%MOD)

def fact(m):
  ret = defaultdict(lambda:0)
  i = 2
  while m > i:
    if m%i == 0:
      ret[i] += 1
      m //= i
    else:
      i += 1
  ret[m] += 1
  return ret


def main():
  N,M = map(int, input().split())
  dct = fact(M)
  ans = 1
  for k in dct:
    ans = (ans * combi(dct[k]+N-1, N-1))%MOD
  print(ans)


if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import defaultdict
from math import factorial


MOD = 10**9+7

def mul(a,b):
  return (a*b) % MOD

def power(a,b):
  ## 二分累乗法
  if   b==0   : return 1
  elif b==1   : return a % MOD
  elif b%2==0 : return power(a,b//2)**2 % MOD
  else        : return power(a,b//2)**2 * a % MOD

def div(a,b):
  ## MOD同士の割り算
  return mul(a,power(b,MOD-2))

def combi(a,b):
  return div(factorial(a)%MOD, (factorial(b)*factorial(a-b))%MOD)


def fact(m):
  ret = defaultdict(lambda:0)
  i = 2
  while m > i:
    if m%i == 0:
      ret[i] += 1
      m //= i
    else:
      i += 1
  ret[m] += 1
  return ret


def main():
  N,M = map(int, input().split())
  dct = fact(M)
  ans = 1
  for k in dct:
    ans = (ans * combi(dct[k]+N-1, N-1))%MOD
  print(ans)


if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
from collections import Counter
from operator import mul
from functools import reduce
from math import factorial


def get_primes(n):
    t = [1] * (n + 1)
    t[0] = t[1] = 0
    ps = []
    for i in range(n + 1):
        if t[i] == 0:
            continue
        ps.append(i)
        for j in range(i, n + 1, i):
            t[j] = 0
    return ps


def solve(s):
    n, m = map(int, s.split())
    if m == 1:
        return 1
    ps = get_primes(int(m**0.5) + 1)
    divisor = []
    tmp = m
    for p in ps:
        while tmp % p == 0:
            divisor.append(p)
            tmp //= p
        if p == 1:
            break
    divisor = Counter(divisor)
    divs = {m}
    for k, v in divisor.items():
        divs.update({ed // (k**j) for ed in divs for j in range(v + 1)})
    divisor = sorted(list(divs))
    del divisor[0]

    def search(ded, use, j):
        if ded == 1:
            # print("{} {} {}".format(ded, use, j))
            count = Counter(use)
            base = reduce(mul, range(n - len(use) + 1, n + 1))
            for v in list(count.values()):
                base //= factorial(v)
            # print(base)
            return base
        if len(use) >= n:
            return 0

        tmp = [
            search(ded // d, use + [d], i + j) for i, d in enumerate(divisor[j:]) if ded % d == 0
        ]
        return sum(tmp) if tmp else 0

    return search(m, [], 0) % (10**9 + 7)


print(solve(input()))

Submission status: Wrong Answer

Solution code:
from collections import Counter
from operator import mul
from functools import reduce
from math import factorial


def solve(s):
    n, m = map(int, s.split())
    if m == 1:
        return 1
    divisor = [2] if m % 2 == 0 else []
    for i in range(3, int(m**0.5) + 1, 2):
        if m % i == 0:
            divisor.append(i)
    divisor += [m // d for d in divisor[::-1]] + [m]
    divisor = sorted(list(set(divisor)))
    ld = len(divisor)

    def search(ded, use, j):
        if ded == 1:
            # print("{} {} {}".format(ded, use, j))
            count = Counter(use)
            base = reduce(mul, range(n - len(use) + 1, n + 1))
            for v in list(count.values()):
                base //= factorial(v)
            # print(base)
            return base
        if len(use) >= n:
            return 0

        tmp = [
            search(ded // divisor[i], use + [divisor[i]], i)
            for i in range(j, ld)
            if ded % divisor[i] == 0
        ]
        return sum(tmp) if tmp else 0

    return search(m, [], 0) % (10**9 + 7)


print(solve(input()))

Submission status: Wrong Answer

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

factors=[]
p = 2
cnt = 0
while M > 1:
    if M % p == 0:
        M = M // p
        cnt += 1
    elif p*p < M:
        if p == 2:
            p = 3
        else:
            p += 2
        if cnt > 0:
            factors.append(cnt)
        cnt = 0
    else:
        if cnt > 0:
            factors.append(cnt)
            cnt = 0
        factors.append(1)

if cnt > 0:
    factors.append(cnt)

MOD = 10**9+7
def permutation(n,m):
    ret = 1
    for i in range(n-m+1, n+1):
        ret = (ret * i) % MOD
    return ret
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0
def inv(n):
    g,x,y = xgcd(n, MOD)
    return g

def combination(n,m):
    return permutation(n,m) * inv(permutation(m,m))
ans = 1
for f in factors:
    ans = (ans * combination(N+f-1, f)) % MOD
print(ans)

Submission status: Wrong Answer

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

factors=[]
p = 2
cnt = 0
while M > 1:
    if M % p == 0:
        M = M // p
        cnt += 1
    elif p*p < M:
        if p == 2:
            p = 3
        else:
            p += 2
        if cnt > 0:
            factors.append(cnt)
        cnt = 0
    else:
        if cnt > 0:
            factors.append(cnt)
            cnt = 0
        factors.append(1)

if cnt > 0:
    factors.append(cnt)

MOD = 10**9+7
def permutation(n,m):
    ret = 1
    for i in range(n-m+1, n+1):
        ret = (ret * i) % MOD
    return ret
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0
def inv(n):
    g,x,y = xgcd(n, MOD)
    return g

def combination(n,m):
    return permutation(n,m) * inv(permutation(m,m))
ans = 1
for f in factors:
    ans = (ans + combination(N+f-1, f)) % MOD
print(ans)