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: Accepted

Solution code:
class Combination:                                      # 計算量は O(n_max + log(mod))
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):                     # 階乗(= n_max !)の逆元を生成
            f = f * i % mod                             # 動的計画法による階乗の高速計算
            fac.append(f)                               # fac は階乗のリスト
        f = pow(f, mod-2, mod)                          # 階乗から階乗の逆元を計算。フェルマーの小定理より、　a^-1 = a^(p-2) (mod p) if p = prime number and p and a are coprime
                                                        # python の pow 関数は自動的に mod の下での高速累乗を行ってくれる
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):                   # 上記の階乗の逆元から階乗の逆元のリストを生成（＝ facinv ）
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()


    def __call__(self, n, r):  # self.C と同じ
        if not 0 <= r <= n: return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def H(self, n, r):                                  # (箱区別:〇　ボール区別:×　空箱:〇)　重複組み合わせ nHm
        if (n == 0 and r > 0) or r < 0: return 0
        return self.fac[n+r-1] * self.facinv[r] % self.mod * self.facinv[n-1] % self.mod


def prime_factors(n):       # 戻り値はiterable type
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            yield i             # whileループを進めるごとにイテレータに値を貯め続ける
    if n > 1:
        yield n

from collections import Counter
MOD = 10**9 + 7
N, M = map(int, input().split())
C = Combination(10**6)
A = list(prime_factors(M))
B = Counter(A)
res = 1
for value in B.values():
    res *= C.H(N,value)%MOD
print(res%MOD)

Submission status: Accepted

Solution code:
from collections import Counter
from functools import reduce
import operator
product = lambda it: reduce(operator.mul,it,1)

def comb(n, max_k, mod):
    """
    (n,k) := n個からk個選ぶ組み合わせ
    k = 0~max_Kまでを計算して返す
    """
    res = [1]*(max_k+1)
    t = 1
    for i in range(max_k+1):
        res[i] *= t
        t *= n-i
        t %= mod

    n = reduce(lambda x,y: (x*y)%mod, range(1,max_k+1), 1)
    n = pow(n, mod-2, mod)

    for i in reversed(range(max_k+1)):
        res[i] *= n
        res[i] %= mod
        n *= i
        n %= mod
    return res

# 素因数分解
def prime_factors(n):
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            yield i
    if n > 1:
        yield n

MOD = 10**9+7
N,M = map(int,input().split())

factors = Counter(prime_factors(M))

res = 1

for c in factors.values():
    res *= comb(N-1+c,c,MOD)[-1]
    res %= MOD

print(res)

Submission status: Accepted

Solution code:
p = 10**9+7
def pow(x,m):
    if m==0:
        return 1
    if m==1:
        return x
    if m%2==0:
        return (pow(x,m//2)**2)%p
    else:
        return (x*(pow(x,(m-1)//2)**2)%p)%p
N,M = map(int,input().split())
A = [1 for _ in range(N+100)]
for i in range(2,N+100):
    A[i] = (A[i-1]*i)%p
B = [1 for _ in range(N+100)]
B[N+100-1] = pow(A[N+100-1],p-2)
for i in range(N+100-2,1,-1):
    B[i] = (B[i+1]*(i+1))%p
P = [1 for _ in range(10**5)]
P[0]=0
P[1]=0
for i in range(2,int((10**5)**0.5)+1):
    for j in range(i*i,10**5,i):
        P[j] = 0
Q = []
for i in range(2,10**5):
    if P[i]==1:
        Q.append(i)

C = {q:0 for q in Q}
for q in Q:
    if M%q==0:
        while M%q==0:
            M = M//q
            C[q] += 1
if M>1:
    C[M] = 1
    Q.append(M)
prod = 1
for q in Q:
    k = C[q]
    a = A[k+N-1]
    a = (a*B[N-1])%p
    a = (a*B[k])%p
    prod = (prod*a)%p
print(prod)

Submission status: Accepted

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

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

mod = 10**9+7

import math
def factorize(n):
    d = {}
    temp = int(math.sqrt(n))+1
    for i in range(2, temp):
        while n%i== 0:
            n //= i
            if i in d:
                d[i] += 1
            else:
                d[i] = 1
    if d == {}:
        d[n] = 1
    else:
        if n in d:
            d[n] += 1
        elif n != 1:
            d[n] =1
    return d

mod = 10**9+7
N = 10**6
fac = [1]*(N+1)
finv = [1]*(N+1)
for i in range(N):
    fac[i+1] = fac[i] * (i+1) % mod
finv[-1] = pow(fac[-1], mod-2, mod)

for i in reversed(range(N)):
    finv[i] = finv[i+1] * (i+1) % mod

def cmb1(n, r, mod):
    if r <0 or r > n:
        return 0
    r = min(r, n-r)
    return fac[n] * finv[r] * finv[n-r] % mod

d = factorize(m)
ans = 1
for k, v in d.items():
    ans *= cmb1(v+n-1, n-1, mod)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
N_MAX = 10**6
MOD = 10**9 + 7
fac, finv, inv = [0]*N_MAX ,[0]*N_MAX, [0]*N_MAX
def com_init():
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 1, 1
    inv[1] = 1
    for i in range(2, N_MAX):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

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


def factorization(n):
    pf_cnt = {}
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i == 0:
            cnt = 0
            while temp%i == 0:
                cnt += 1
                temp //= i
            pf_cnt[i] = cnt

    if temp != 1: pf_cnt[temp] = 1
    if not pf_cnt: pf_cnt[n] = 1

    return pf_cnt



def main():
    n,m = map(int, input().split())
    if m == 1:
        print(1)
        exit()
    facd = factorization(m)
    com_init()
    ans = 1
    for k,v in facd.items():
        comb = com(v+n-1,n-1)
        ans *= comb
        ans%=MOD

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def factorize(n):
    fct = []
    
    for i in range(2, int(n**0.5)+1):
        c = 0
        
        while n%i==0:
            n //= i
            c += 1
            
        if c>0:
            fct.append((i, c))
    
    if n>1:
        fct.append((n, 1))
    
    return fct
    
MAX = 10**5+100
MOD = 10**9+7
fact = [0]*MAX #fact[i]: i!
inv = [0]*MAX #inv[i]: iの逆元
finv = [0]*MAX #finv[i]: i!の逆元
fact[0] = 1
fact[1] = 1
finv[0] = 1
finv[1] = 1
inv[1] = 1
    
for i in range(2, MAX):
    fact[i] = fact[i-1]*i%MOD
    inv[i] = MOD-inv[MOD%i]*(MOD//i)%MOD
    finv[i] = finv[i-1]*inv[i]%MOD

def C(n, r):
    if n<r:
        return 0
    if n<0 or r<0:
        return 0
    return fact[n]*(finv[r]*finv[n-r]%MOD)%MOD

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

for _, c in fct:
    ans *= C(N-1+c, c)
    ans %= MOD

print(ans)

Submission status: Accepted

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

MAXN = N+100
fac = [1,1] + [0]*MAXN
finv = [1,1] + [0]*MAXN
inv = [0,1] + [0]*MAXN
for i in range(2,MAXN+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD
def comb(n,r):
    if n < r: return 0
    if n < 0 or r < 0: return 0
    return fac[n] * (finv[r] * finv[n-r] % MOD) % MOD

from collections import Counter
def factorize(n):
    d = Counter()
    m = 2
    while m*m <= n:
        while n%m == 0:
            n //= m
            d[m] += 1
        m += 1
    if n > 1:
        d[n] += 1
    return d

ans = 1
f = factorize(M)
for v in f.values():
    c = comb(N+v-1, v)
    ans *= c
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
# from scipy.misc import comb

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])

    return result

def solve(n,m):
    maxdiv = int(m**0.5)
    l = []
    tmp = 2
    num = 0
    while tmp <= maxdiv:
        if m % tmp == 0:
            m /= tmp
            num += 1
        else:
            tmp += 1
            if num != 0:
                l.append(num)
                num = 0
    if m != 1:
        l.append(1)
    res = 1
    for div in l:
        tmp = cmb(n+div-1,div)%(10**9+7)
        res = res * tmp % (10**9+7)
    return int(res)
        

if __name__ == '__main__':
    n,m = map(int,input().split())
    print(solve(n,m))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
def modinv(a, mod):
    return pow(a, mod - 2, mod)

MOD = 10**9+7
class Factorial:
    def __init__(self, n, mod):
        # O(n + log mod)
        self.f = f =[0] * (n + 1)
        f[0] = b = 1
        for i in range(1, n + 1):
            f[i] = b = b * i % mod
        self.inv = inv = [0] * (n + 1)
        inv[n] = b = modinv(self.f[n], mod) # pow(self.f[n], -1, mod) が Google Colab, Python ver. が低く Error
        for i in range(n, 0, -1):
            inv[i - 1] = b = b * i % mod
        self.mod = mod
    
    def __call__(self, n, k):  # self.C() と同じ
        return self.C(n, k)

    def factorial(self, i):
        return self.f[i]

    def ifactorial(self, i):
        return self.inv[i]

    def C(self, n, k):
        if not 0 <= k <= n: return 0
        return self.f[n] * self.inv[n - k] * self.inv[k] % self.mod

    def P(self, n, k):
        if not 0 <= k <= n: return 0
        return self.f[n] * self.inv[n - k] % self.mod

    def H(self, n, k):
        if (n == 0 and k > 0) or k < 0: return 0
        return self.f[n + k - 1] * self.inv[k] % self.mod * self.inv[n - 1] % self.mod

def factorize(n) -> list:
    b, e = 2, 0
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            e += 1
        if e:
            fct += (b, e), # b,
        b += 1
        e = 0
    if n > 1:
        fct += (n, 1), # n,
    return fct

n, m = map(int, input().split())
F = Factorial(n + 30, MOD)
c = 1
for _, E in factorize(m):
    c = c * F.H(n, E) % MOD
print(c)

Submission status: Accepted

Solution code:
MOD=10**9+7
UPPERLIMIT=2*10**5
MODMUL=[1, 1]+[0]*(UPPERLIMIT-1)
for i in range(2, UPPERLIMIT+1):
  MODMUL[i]=MODMUL[i-1]*i%MOD
MODDIV=[1]*UPPERLIMIT+[pow(MODMUL[-1], MOD-2, MOD)]
for i in range(UPPERLIMIT, 0, -1):
  MODDIV[i-1]=MODDIV[i]*i%MOD
def MODCOMB(n, r):
  return (((MODMUL[n]*MODDIV[r])%MOD)*MODDIV[n-r])%MOD

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

from collections import defaultdict
def PrimeFactorization(x):
  out=defaultdict(int)
  for i in range(2, int(pow(x, 1/2))+1):
    while x%i==0:
      out[i]+=1
      x//=i
  if x>1:
    out[x]+=1
  return out

primenums=PrimeFactorization(M)
ans=1
for x in primenums.values():
  ans*=MODCOMB(N+x-1, N-1)
  ans%=MOD
  
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
MOD=10**9+7
 
def cmb(n, r, p):
  numerator = 1
  for i in range(n-r+1, n+1):
    numerator = numerator * i % p
  denominator = 1
  for j in range(1, r+1):
    denominator = denominator * j % p
  denominator = pow(denominator, p-2, p)
  return (numerator * denominator)%p
 
def factorization(n):
  l = []
  t = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if t%i==0:
      cnt=0
      while t%i==0:
        cnt+=1
        t //= i
      l.append([i, cnt])
  if t!=1:
    l.append([t, 1])
  if l==[]:
    l.append([n, 1])
  return l
 
ans=1
F=factorization(M)
for i in range(len(F)):
  f=F[i][1]
  ans*=cmb(f+N-1,f,MOD)
  ans%=MOD

if M==1:
  print(1)
else:
  print(ans)

Submission status: Accepted

Solution code:
import collections
import math
from operator import mul
from functools import reduce
N,M = list(map(int,input().split()))

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

c = collections.Counter(prime_factorize(M))
primeFactorizeList = list(c.values())
answer = 1
for i in primeFactorizeList:
    answer *= combinations_count(i+N-1, i)
    answer = answer % (10 ** 9 + 7)
print(int(answer))

Submission status: Accepted

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

import math

def prime_fac(n):
  p_lis = []
  temp = n

  for i in range(2, int(math.sqrt(n)) + 1):
    if temp % i == 0:
      cnt = 0
      while temp % i == 0:
        cnt += 1
        temp //= i
      p_lis.append([i, cnt])
  if temp != 1:
    p_lis.append([temp, 1])
  if p_lis == []:
    p_lis.append([n, 1])

  return p_lis

mod = 10 ** 9 + 7
MAX = N + 50
fac = [1, 1]
finv = [1, 1]
inv = [0, 1]

def comb(n, r):
  if n < r:
    return 0
  else:
    return fac[n] * ( finv[r] * finv[n-r] % mod ) % mod
 
for i in range(2, MAX + 1):
  fac.append( ( fac[-1] * i ) % mod )
  inv.append( mod - ( inv[mod % i] * (mod // i) % mod ) )
  finv.append( finv[-1] * inv[-1]  % mod )

ans = 1

for p, a in prime_fac(M):
  if a == p == 1:
    break
  ans *= comb(N+a-1, a)
  ans %= mod

print(ans)

Submission status: Accepted

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

import math

def prime_fac(n):
  p_lis = []
  temp = n

  for i in range(2, int(math.sqrt(n)) + 1):
    if temp % i == 0:
      cnt = 0
      while temp % i == 0:
        cnt += 1
        temp //= i
      p_lis.append([i, cnt])
  if temp != 1:
    p_lis.append([temp, 1])
  if p_lis == []:
    p_lis.append([n, 1])

  return p_lis

mod = 10 ** 9 + 7
MAX = 10 ** 6
fac = [1, 1]
finv = [1, 1]
inv = [0, 1]

def comb(n, r):
  if n < r:
    return 0
  else:
    return fac[n] * ( finv[r] * finv[n-r] % mod ) % mod
 
for i in range(2, MAX + 1):
  fac.append( ( fac[-1] * i ) % mod )
  inv.append( mod - ( inv[mod % i] * (mod // i) % mod ) )
  finv.append( finv[-1] * inv[-1]  % mod )

ans = 1

for p, a in prime_fac(M):
  if a == p == 1:
    break
  ans *= comb(N+a-1, a)
  ans %= mod

print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M = mapint()
mod = 10**9+7

pos = {}
neg = {}
n = 1
pos[0] = 1
neg[0] = 1
for i in range(1, 500000):
    n *= i
    n %= mod
    pos[i] = n
    neg[i] = pow(n, mod-2, mod)

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

from collections import Counter
primes = prime_factorize(M)
c = Counter(primes)
primes = list(set(primes))
leng = len(primes)
ans = 1
for i in range(leng):
    p = primes[i]
    n = c[p]
    ans *= pos[N+n-1]*neg[n]*neg[N-1]
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
#import heapq
from fractions  import gcd
#input=sys.stdin.readline
import bisect
def factorize(n):
    fct={}
    temp=n
    if temp<4:
        fct[temp]=1
    else:
        e=0
        while temp%2==0:
            temp=temp//2
            e+=1
        if e>0:
            fct[2]=e
    
    for b in range(3,int(n**0.5)+1,2):
        e=0
        while temp%b == 0:
            temp=temp//b
            e+=1
        if e>0:
            fct[b]=e
    if temp!=1:
        fct[temp]=1
    return fct
n,m=map(int,input().split())
f=factorize(m)
Mod=10**9+7
M=10**7 #書き換え
fac=[0]*M
finv=[0]*M
inv=[0]*M

#finvに逆元、facに階乗のmod
def COMinit():
  fac[0]=fac[1]=1
  finv[0]=finv[1]=1
  inv[1]=1
  for i in range(2,M):
    fac[i]=(fac[i-1]*i%Mod)%Mod
    inv[i]=Mod-inv[Mod%i]*(Mod//i) %Mod
    finv[i]=(finv[i-1]*inv[i]%Mod)%Mod
def COM(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)%Mod

COMinit()
ans=1
if m==1:
  print(1)
  exit()
for i in f:
    a=f[i]
    ans*=COM(n-1+a,n-1)
    ans%=Mod
print(ans)

Submission status: Accepted

Solution code:
#素因数分解
def soinsu_bunkai(m):
    pf={}

    for i in range(2,int(m**0.5)+1):
        while m%i==0:
            pf[i]=pf.get(i,0)+1
            m//=i
    if m>1:
        pf[m]=1
    return pf

# 組み合わせの総数 p=10**9+7 で割ったあまりを求める Satoooh Blog 2020/02/27 4分 
"""n<10**7 , p は素数"""
def cmb(n, r, p):

    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p



# 初期入力
from collections import Counter
import sys
input = sys.stdin.readline  #文字列では使わない
mod =10**9 +7
p =mod
N,M = map(int, input().split())
a =soinsu_bunkai(M)
ans =1

n = 10 **5 +100  # n は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

#mod p における n の逆元の計算
for i in range(2, n + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

for i in a.values():
    x =cmb(N +i -1,i,mod)
    ans *=x
print(ans %mod)

Submission status: Accepted

Solution code:
#素因数分解
def soinsu_bunkai(m):
    pf={}

    for i in range(2,int(m**0.5)+1):
        while m%i==0:
            pf[i]=pf.get(i,0)+1
            m//=i
    if m>1:
        pf[m]=1
    return pf

# 組み合わせの総数 p=10**9+7 で割ったあまりを求める Satoooh Blog 2020/02/27 4分 
"""n<10**7 , p は素数"""
def cmb(n, r, p):

    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p



# 初期入力
from collections import Counter
import sys
input = sys.stdin.readline  #文字列では使わない
mod =10**9 +7
p =mod
N,M = map(int, input().split())
a =soinsu_bunkai(M)
ans =1

n = 10 ** 6  # n は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

#mod p における n の逆元の計算
for i in range(2, n + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

for i in a.values():
    x =cmb(N +i -1,i,mod)
    ans *=x
print(ans %mod)

Submission status: Accepted

Solution code:
mod1,mod2=10**9+7,998244353
mod=mod1
n,m=map(int,input().split())
mod=10**9+7
fact=[1]*(n+50+1)
inv=[1]*(n+50+1)
for i in range(2,n+50+1):
    fact[i]=i*fact[i-1]%mod
inv[-1]=pow(fact[-1],mod-2,mod)
for i in range(n+50,1,-1):
    inv[i-1]=inv[i]*i%mod
def comb(x,y):return fact[x]*inv[y]%mod*inv[x-y]%mod if x>=y>=0 else 0
from math import floor,sqrt
ans=1
for i in  range(2,floor(sqrt(m))+1):
    if m%i:continue
    cnt=0
    while m%i==0:
        cnt+=1
        m//=i
    ans=ans*comb(n-1+cnt,cnt)%mod
if m!=1:
    ans=ans*comb(n,1)%mod
print(ans)

Submission status: Accepted

Solution code:
import collections
import math

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


def prime_factorize(n: int) -> list:
    primes = []
    while n % 2 == 0:
        primes.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            primes.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        primes.append(n)
    return primes


def comb(n: int, r: int) -> int:
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


if M == 1:
    print(1)
else:
    primes = collections.Counter(prime_factorize(M))
    res = 1
    for freq in primes.values():
        res *= comb(N + freq - 1, freq)
        res %= (10 ** 9 + 7)
    print(res)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
dic = {}
if N == 1:
    print(1)
    exit()
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        if 2 not in dic:
            dic[2] = 1
        else:
            dic[2] += 1
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            if f not in dic:
                dic[f] = 1
            else:
                dic[f] += 1
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        if n not in dic:
            dic[n] = 1
        else:
            dic[n] += 1
        a.append(n)
    return a

n = 10 ** 9
k = 2 * 10 ** 5
mod = 10**9 + 7

modinv_table = [-1] * (k+1)
modinv_table[1] = 1
for i in range(2, k+1):
    modinv_table[i] = (-modinv_table[mod % i] * (mod // i)) % mod

def binomial_coefficients(n, k):
    ans = 1
    for i in range(k):
        ans *= n-i
        ans *= modinv_table[i + 1]
        ans %= mod
    return ans

prime_factorize(M)
res = 1
for k, v in dic.items():
    if v == 1:
        res *= N % mod
    else:
        res *= binomial_coefficients((v + N - 1), (N - 1)) % mod
print(res % mod)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
mod = 10**9+7
modp = mod
max_n = 10 ** 6 + 1               # 必要分だけ用意する
fact = [1, 1] + [0]*max_n     # fact[n] = (n! mod modp)
factinv = [1, 1] + [0]*max_n  # factinv[n] = ((n!)^(-1) mod modp)
inv = [0, 1] + [0]*max_n      # factinv 計算用

def cmb(n, r, p):
    assert n < p, 'n is less than modp'
    assert n < max_n, 'n in less than max_n'
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return (fact[n] * (factinv[r] * factinv[n-r])%p) % p

for i in range(2, max_n + 1):
    fact[i] = (fact[i-1] * i) % modp
    inv[i] = (-inv[modp % i] * (modp // i)) % modp
    factinv[i] = (factinv[i-1] * inv[i]) % modp

def factorization(m):
    arr = []
    temp = m
    # 一旦負にするとceilと同じ挙動となる。//1はfloatを返すのでintが必要
    for i in range(2, int(-(-m**0.5//1))+1):
        if temp%i==0:
            cnt = 0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    
    if temp!=1:
        arr.append([temp, 1])
    
    if arr==[]:
        arr.append([n, 1])
    return arr

arr = factorization(m)

ans = 1
for k, v in arr:
    temp = cmb(v+n-1, n-1, mod)
    ans = (ans * temp) % mod
if m == 1:
    print(1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import collections
import math

def prime_factorize(n):
  a = []
  while n % 2 == 0:
    a.append(2)
    n //= 2
  f = 3
  while f * f <= n:
    if n % f == 0:
      a.append(f)
      n //= f
    else:
      f += 2
  if n != 1:
    a.append(n)
  return a

def nCr(n,r):
  #print(n,r)
  return (FAC[n]*INV[n-r]*INV[r])%MOD

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

MOD = 10**9 + 7
FAC = [1]
INV = [1]
N = int(math.log(m,2))+n+1
for i in range(1,N+1):
  FAC.append((FAC[i-1]*i) % MOD)
  INV.append(pow(FAC[-1],MOD-2,MOD))

c = collections.Counter(prime_factorize(m))
#print(c)
ans = 1
for k,v in c.items():
  #print(k,v)
  ans *= nCr(v+n-1,v)
  ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

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

fact = []

X = M
i = 2
while i ** 2 <= X:
    v = 0
    while M % i == 0:
        M //= i
        v += 1
    if v != 0:
        fact.append(v)
    i += 1
if M != 1:
    fact.append(1)

MAX = 2 * 10 ** 5
MOD = 10 ** 9 + 7

fac = [0 for i in range(MAX)]
finv = [0 for i in range(MAX)]
inv = [0 for i in range(MAX)]

def comInit(mod):
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 1, 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i - 1] * inv[i] % mod


def com(n, r, mod):
    if n < r:
        return 0
    if n < 0 or r < 0:
        return 0
    return fac[n] * (finv[r] * finv[n - r] % mod) % mod
    
comInit(MOD)


ans = 1
for f in fact:
    ans *= com(f + N - 1, N - 1, MOD)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,M = IL()
ans = 1
for p,n in factorization(M):
  if p!=1:
    ans *= nCr(n+N-1,N-1)
    ans %= MOD
print(ans)