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:
N,M=map(int,input().split())

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(cnt)

    if temp!=1:
        arr.append(1)

    if arr==[]:
        arr.append(0)

    return arr
     
p=factorization(M)#素因数分解して次数を調べる

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

mod=10**9 + 7
fact=[1,1]
factinv=[1,1]
inv=[0,1]
 
N2=N+max(p)    

for i in range(2, N2 + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)
    

        
ans=1
for i in range(len(p)):
    ans*=cmb(p[i]+N-1,p[i],mod)
    ans%=mod

print(ans)

Submission status: Accepted

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

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(cnt)

    if temp!=1:
        arr.append(1)

    if arr==[]:
        arr.append(1)

    return arr
     
p=factorization(M)#素因数分解して次数を調べる

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

mod=10**9 + 7
fact=[1,1]
factinv=[1,1]
inv=[0,1]
 
N2=N+max(p)    

for i in range(2, N2 + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)
    

        
ans=1
for i in range(len(p)):
    ans*=cmb(p[i]+N-1,p[i],mod)
    ans%=mod
if M==1:
    ans=1
print(ans)

Submission status: Accepted

Solution code:
N, M = [int(_) for _ in input().split()]

MOD = 10**9+7

def primes(n):
    from math import sqrt
    mn = int(sqrt(n)) + 2
    p = [1] * mn
    for x in range(2, mn):
        if p[x]:
            y = x * x
            while y < mn:
                p[y] = 0
                y += x
    return (i for i in range(2, mn) if p[i])

def calc(M):
    result = {}
    for n in primes(M):
        if M % n == 0:
            result[n] = 1
            M //= n
        while M % n == 0:
            result[n] += 1
            M //= n
    if M > 1:
        result[M] = 1
    return result

def C(x, y):
    n = min(y, x - y)
    r = 1
    for i in range(n):
        r = r * (x - i)
    for i in range(n):
        r = r // (i + 1)
    return r

cs = calc(M)

result = 1

for x in cs.values():
    result = result * C(N+x-1, N-1) % MOD

print(result)

Submission status: Accepted

Solution code:
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 #出力の制限
N = 2*10**5+5
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 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


n,m=map(int,input().split())
A=factorization(m)
ans=1
if m==1:
  print(ans)
else:
  for i in range(len(A)):
    ans=ans*cmb(n+A[i][1]-1,A[i][1],mod)
  print(ans%(10**9+7))

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split()))
data = dict()
div = 2
mod = 10**9+7
#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
#a/b = a*(b`)となるb`を求める
def mod_inv(a,mod):
    x = extgcd(a,mod)[0]
    return (mod+x%mod)%mod
def mod_factorial(n):
    ans = 1
    while n >= 2:
        ans  = (ans * n) % mod
        n -= 1
    return ans
while m > 1:
    count = 0
    flag = False
    while m % div == 0:
        if div not in data:
            data[div] = 0
        flag = True
        m /= div
        count += 1
        data[div] += 1
    div += 1
ans = 1
for i in data.keys():
    p = mod_factorial(data[i]+n-1)
    q = mod_inv(mod_factorial(data[i]), mod)
    r = mod_inv(mod_factorial(n-1), mod)
    ans *= p * q
    ans %= mod
    ans *= r
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict

# mod mでの二項係数を求める
class BiCoeff(object):
    def __init__(self, MAX, m):
        super(BiCoeff, self).__init__()
        fac = [0]*MAX
        finv = [0]*MAX
        inv = [0]*MAX

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

        self.MAX = MAX
        self.m = m
        self.fac = fac
        self.finv = finv
        self.inv = inv

    def calc(self,n,k):
        if n<k:
            return 0
        if n<0 or k<0:
            return 0
        return (self.fac[n] * (self.finv[k]*self.finv[n-k])%self.m)%self.m

MOD = 10**9+7
n, m = map(int, input().split())

pl = defaultdict(int)
x = m
p = 2
while p*p<x+10:
    while x%p==0:
        pl[p] += 1
        x //= p
    p += 1
if x>1:
    pl[x] += 1


coeff = BiCoeff(10**6, MOD)
res = 1
for k in pl:
    res *= coeff.calc(n+pl[k]-1, pl[k])
    res %= MOD
print(res)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7


def mod_pow(a, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        half_p = p // 2
        half = mod_pow(a, half_p)
        return half * half % mod
    else:
        return a * mod_pow(a, p - 1) % mod


def calc_comb(a, b):
    if b > a - b:
        return calc_comb(a, a - b)

    ans_mul = 1
    ans_div = 1
    for i in range(b):
        ans_mul *= (a - i)
        ans_div *= (i + 1)
        ans_mul %= mod
        ans_div %= mod

    ans = ans_mul * mod_pow(ans_div, mod - 2) % mod
    return ans


N, M = map(int, input().split())
ans = 1
rest = M
for i in range(2, int(M ** 0.5) + 1):
    if rest % i == 0:
        cnt = 0
        while rest % i == 0:
            cnt += 1
            rest = rest // i
        ans *= calc_comb(N + cnt - 1, N - 1)
        ans %= mod
if rest != 1:
    ans *= calc_comb(N + 1 - 1, N - 1)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
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

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
SIZE = 10 ** 5 * 2 + 1
g1 = [1, 1]
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
 
for i in range(2, SIZE + 1 ):
  g1.append((g1[-1] * i) % MOD)
  inverse.append((-inverse[MOD % i] * (MOD // i) ) % MOD)
  g2.append((g2[-1] * inverse[-1]) % MOD)

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

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

answer = 1
for p, a in factorization(M):
  answer = (answer * cmb(N - 1 + a, a, MOD)) % MOD

print(answer)

Submission status: Accepted

Solution code:
import math
from collections import Counter

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

K = 50
fact = [0] * (n+1+K)
ifact = [0] * (n+1+K)
fact[0] = 1
for i in range(1,n+1+K):
    fact[i] = fact[i-1] * i % mod
ifact[n+K] = pow(fact[n+K], mod-2, mod)
for i in reversed(range(1,n+1+K)):
    ifact[i-1] = ifact[i] * i % mod

def comb(n, k):
    return fact[n] * ifact[n-k] % mod * ifact[k] % mod

def getprime(n):
    primes = []
    i = 2
    while n >= i * i:
        while n % i == 0:
            n //= i
            primes.append(i)
        i += 1
    if n != 1:
        primes.append(n)
    return primes

ans = 1
counter = Counter(getprime(m))
for k in counter.values():
    ans *= comb(n+k-1, k)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
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
 
N,M=map(int,input().split())
primes0=prime_factorize(M)
keys=list(set(primes0))
primes={}
for i in range(len(keys)):
  k=keys[i]
  primes[k]=0
  for j in range(len(primes0)):
    if primes0[j]==k:
      primes[k]+=1
 
def cmb(n, k, mod, fac, ifac): #calc nCk under mod
    if n < k or n < 0 or k < 0:
        return 0
    else: 
        k = min(k, n-k)
        return fac[n] * ifac[k] * ifac[n-k] % mod
 
def make_tables(mod, n): #Make factorial and inverse tables under mod 
    fac = [1, 1] # factorial table
    ifac = [1, 1] #factorial of inverse table
    inverse = [0, 1] #inverse
 
    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod//i)) % mod)
        ifac.append((ifac[-1] * inverse[-1]) % mod)
    return fac, ifac
 
mod=10**9+7
fac,ifac=make_tables(mod,N*10)
ans=1
for i in range(len(keys)):
  ans*=cmb(N+primes[keys[i]]-1, primes[keys[i]], mod, fac, ifac)
  ans%=mod
print(ans)

Submission status: Accepted

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

n = 10**5
prime = {i for i in range(2,n)}
for i in range(2,n):
    if i in prime:
        for j in range(i*2,n,i):
            if j in prime:
                prime.remove(j)
                
dic={some:0 for some in prime}

def prime_factorization(N):
    for some in prime:
        if N%some==0:
            while N%some==0:
                N=N//some
                dic[some]+=1
        else:
            pass
    if N!=1:
        dic[N]=1
prime_factorization(M)   

def find_power(n,mod):
    # 0!からn!までのびっくりを出してくれる関数(ただし、modで割った値に対してである）
    powlist=[0]*(n+1)
    powlist[0]=1
    powlist[1]=1
    for i in range(2,n+1):
        powlist[i]=powlist[i-1]*i%(mod)
    return powlist

def find_inv_power(n):
    #0!からn!までの逆元を素数10**9+7で割ったあまりリストを作る関数
    powlist=find_power(n,10**9+7)
    check=powlist[-1]
    first=1
    uselist=[0]*(n+1)
    secondlist=[0]*30
    secondlist[0]=check
    secondlist[1]=check**2
    for i in range(28):
        secondlist[i+2]=(secondlist[i+1]**2)%(10**9+7)
    a=format(10**9+5,"b")
    for j in range(30):
        if a[29-j]=="1":
            first=(first*secondlist[j])%(10**9+7)
    uselist[n]=first
    for i in range(n,0,-1):
        uselist[i-1]=(uselist[i]*i)%(10**9+7)
    return uselist

def combi(a,b,n,r,mod):
    if n<r:
        return 0
    elif n>=r:
        return (a[n]*b[r]*b[n-r])%(mod)

P=1
a=find_power(10**5+1000,10**9+7)
b=find_inv_power(10**5+1000)
for some in dic.values():
    P*=combi(a,b,some+N-1,N-1,10**9+7)
    P=P%(10**9+7)
print(P)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
mod = int(1e+9 + 7)
a = mod - 2
ax = []
while a != 0:
  ax = [a%2] + ax[:]
  a //= 2
def inved(x):
  y = 1
  for i in range(len(ax)):
    if ax[i] == 1:
      y *= x
      y %= mod
    if i != len(ax) - 1:
      y *= y
      y %= mod
  return y

p, n = 2, M
L = []
dig = 1
while n != 1:
  i = 0
  while n % p == 0:
    n //= p
    dig *= p
    i += 1
  if i != 0:
    L.append([p, i])
  p += 1
  if p > int(M**(1/2)) and dig != M:
    if L != []:
      L.append([M//dig, 1])
    else:
      L.append([M, 1])
    break

if M == 1:
  print(1)
else:
  prod = 1
  mm = max(x[1] for x in L)
  fact = [1]
  for i in range(N + mm - 1):
    fact.append((fact[i] * (i + 1)) % mod)
  invf = inved(fact[N - 1])
  for i in L:
    pad = (fact[N - 1 + i[1]] * inved(fact[i[1]]) * invf) % mod
    prod *= pad
    prod %= mod
  print(prod)

Submission status: Accepted

Solution code:
import sys

MOD = 10 ** 9 + 7

def make_table(size=10**6, p=MOD):
    fac = [None] * (size + 1)
    fac[0] = 1
    for i in range(size):
        fac[i+1] = fac[i] * (i + 1) % p
    ifac = [None] * (size + 1)
    ifac[size] = pow(fac[size], p-2, p)
    for i in range(size, 0, -1):
        ifac[i-1] = ifac[i] * i % p
    return fac, ifac

fac, ifac = make_table(10**5+30)

def comb(n, r, mod=MOD):
    if r > n or r < 0:
        return 0
    return fac[n] * ifac[r] % mod * ifac[n-r] % mod

from collections import defaultdict
from math import floor, sqrt
def prime_factorize(n):
    res = defaultdict(int)
    while n % 2 == 0:
        res[2] += 1
        n //= 2
    if n == 1:
        return res
    for i in range(3, floor(sqrt(n))+1, 2):
        while n % i == 0:
            res[i] += 1
            n //= i
        if n == 1:
            return res
    res[n] += 1
    return res

n, m = map(int, sys.stdin.readline().split())

def main():
    pfacts = prime_factorize(m)
    res = 1
    for v in pfacts.values():
        res *= comb(n-1+v, v)
        res %= MOD
    return res

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
import sys

MOD = 10 ** 9 + 7

def make_table(size=10**6, p=MOD):
    fac = [None] * (size + 1)
    fac[0] = 1
    for i in range(size):
        fac[i+1] = fac[i] * (i + 1) % p
    ifac = [None] * (size + 1)
    ifac[size] = pow(fac[size], p-2, p)
    for i in range(size, 0, -1):
        ifac[i-1] = ifac[i] * i % p
    return fac, ifac

fac, ifac = make_table()

def comb(n, r, mod=MOD):
    if r > n or r < 0:
        return 0
    return fac[n] * ifac[r] % mod * ifac[n-r] % mod

from collections import defaultdict
from math import floor, sqrt
def prime_factorize(n):
    res = defaultdict(int)
    while n % 2 == 0:
        res[2] += 1
        n //= 2
    if n == 1:
        return res
    for i in range(3, floor(sqrt(n))+1, 2):
        while n % i == 0:
            res[i] += 1
            n //= i
        if n == 1:
            return res
    res[n] += 1
    return res

n, m = map(int, sys.stdin.readline().split())

def main():
    pfacts = prime_factorize(m)
    res = 1
    for v in pfacts.values():
        res *= comb(n-1+v, v)
        res %= MOD
    return res

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
mod = 10**9+7
rng = 101001
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
for i in range(1,rng):
  finv.append(pow(fctr[i],mod-2,mod))
def cmb(n,k):
  if n<0 or k<0:
    return 0
  else:
    return fctr[n]*finv[n-k]*finv[k]%mod
from collections import Counter
N,M = map(int,input().split())
if M == 1:
  print(1)
  exit()
pf = []
while M != 1:
  for i in range(2,int(M**0.5+1)):
    if M%i == 0:
      pf.append(i)
      M = M//i
      break
  else:
    pf.append(M)
    M = 1
cpf = list(Counter(pf).values())
ans = 1
for i in cpf:
  ans = (ans*cmb(N+i-1,i))%mod
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
if N == 1 or M == 1:
    print(1)
    exit()
MOD = 10**9+7
A = []
m = M
for i in range(2, int(M**0.5)+1):
    if m % i == 0:
        m //= i
        k = 1
        while m % i == 0:
            m //= i
            k += 1
        A.append(k)
        if m == 1:
            break
else:
    A.append(1)
B = [0] * max(A)
for a in A:
    B[a-1] += 1
fn_1 = 1
for i in range(1, N):
    fn_1 *= i
    fn_1 %= MOD
ans = 1
fk = fn_1
for i, b in enumerate(B, N):
    fk *= i
    fk %= MOD
    fk *= pow(max(1, i - N + 1), MOD-2, MOD)
    fk %= MOD
    ans *= pow(fk, b, MOD)
    ans %= MOD
    ans *= pow(pow(fn_1, b, MOD), MOD-2, MOD)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')

# 素因数分解
def prime_factorization(n):
    fact=[]
    for i in range(2, int(sqrt(n)) + 1):
        while n % i == 0:
            n //= i
            fact.append(i)
    if n!=1:
        fact.append(n)
    return fact
#mint
class ModInt:
    def __init__(self, x):
        self.x = x % mod
    
    def __str__(self):
        return str(self.x)
    
    __repr__ = __str__

    def __add__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x + other.x)
        else:
            return ModInt(self.x + other)

    __radd__ = __add__
        
    def __sub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x - other.x)
        else:
            return ModInt(self.x - other)

    def __rsub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(other.x - self.x)
        else:
            return ModInt(other - self.x)

    def __mul__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * other.x)
        else:
            return ModInt(self.x * other)

    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * pow(other.x, mod-2,mod))
        else:
            return ModInt(self.x * pow(other, mod - 2, mod))
            
    def __rtruediv(self, other):
        if isinstance(other, self):
            return ModInt(other * pow(self.x, mod - 2, mod))
        else:
            return ModInt(other.x * pow(self.x, mod - 2, mod))
            

    def __pow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(self.x, other.x, mod))
        else:
            return ModInt(pow(self.x, other, mod))
            

    def __rpow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(other.x, self.x, mod))
        else:
            return ModInt(pow(other, self.x, mod))

class BigCombination(object):

    def __init__(self, mod: int=10**9+7, max_n: int=10**6):
        fac, inv=[1], []
        fac_append, inv_append=fac.append, inv.append

        for i in range(1, max_n+1):
            fac_append(fac[-1] * i % mod)

        inv_append(pow(fac[-1], mod-2, mod))

        for i in range(max_n, 0, -1):
            inv_append(inv[-1] * i % mod)

        self.mod, self.factorial, self.inverse=mod, fac, inv[::-1]

    def get_combination(self, n, r):
        if n < r:
            return 0
        return self.factorial[n] * self.inverse[r] * self.inverse[n-r] % self.mod

    def get_permutation(self, n, r):
        if n < r:
            return 0
        return self.factorial[n] * self.inverse[n-r] % self.mod

def main():
    N,M = MI()
    prime = prime_factorization(M)

    ans = ModInt(1)
    B = BigCombination()
    for p in prime:
        cnt = 0
        while M%p == 0:
            M//=p
            cnt += 1
        ans *= B.get_combination(N+cnt-1, N-1)
    print(ans)
        

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

N,M=[int(x) for x in str(input()).split()]
lim=int(M**0.5)+100005




num=10**9+7
x=1
factorial=[1]
for i in range(1,2*10**5+1):
  x=(i*x)%num
  factorial.append(x)
 
rfactorial=[]
for i in factorial:
  rfactorial.append(pow(i,num-2,num))
 

def c(n,k):
  return (((factorial[n]*rfactorial[k])%num)*rfactorial[n-k])%num


ans=1
for i in range(2,int(M**0.5)+2):
  count=0
  while M%i==0:
    count+=1
    M=M//i
  ans=(ans*c(N+count-1,count))%num
if M>1:
  ans=(ans*c(N,1))%num

print(ans)

Submission status: Accepted

Solution code:
#  Copyright: this code was written at 2020. for AtCoder by Silviase

# Lib
import math


def mod_comb(n1, n2):
    return fac_tab[n1] * fac_tab[n2].inv() * fac_tab[n1 - n2].inv()


class ModInt:
    MOD = int(1e9 + 7)

    # int (演算子) ModIntはダメ

    def __init__(self, x):
        self.x = x % self.MOD

    # ModInt(op){ModInt, Int}に対応している
    def __add__(self, other):
        return self.__class__((self.x + other.x) % self.MOD) if isinstance(other, ModInt) else self.__class__(
            (self.x + other) % self.MOD)

    def __sub__(self, other):
        return self.__class__((self.x - other.x) % self.MOD) if isinstance(other, ModInt) else self.__class__(
            (self.x - other) % self.MOD)

    def __mul__(self, other):
        return self.__class__((self.x * other.x) % self.MOD) if isinstance(other, ModInt) else self.__class__(
            (self.x * other) % self.MOD)

    # 逆元をかけることに等しい
    def __truediv__(self, other):
        return self.__mul__(other.inv()) if isinstance(other, ModInt) else self.__mul__(ModInt(other).inv())

    # powは第三引数まで指定することで最適化される
    def __pow__(self, power, Modulo=MOD):
        return self.__class__(pow(self.x, power, Modulo))

    def _fac(self):
        mx = ModInt(1)
        for _i in range(self.x, 1, -1):
            mx = mx * _i
        return mx

    # mi_C_kをModInt型で返す
    def _comb(self, _k):
        if isinstance(_k, ModInt):
            if self < _k:
                return ModInt(0)
            return self._fac() * _k._fac().inv() * (self - _k)._fac().inv()
        else:
            if self < _k:
                return ModInt(0)
            return self._fac() * ModInt(_k)._fac().inv() * ModInt(self.x - _k)._fac().inv()

    def inv(self):
        return self.__pow__(self.MOD - 2)

    def __str__(self):
        return str(self.x)

    def __lt__(self, other):
        return self.x < other.x if isinstance(other, ModInt) else self.x < other


# Lib

# Code
# 素因数分解はルートまで,それ以上で残ったら一つ追加していけばいいことがわかる
# 各素因数についてx個あるのであれば(n+x)Cxであればいいことがわかる
# factに関しては毎回計算すると爆発するのでtableを持っておけばいいことがわかる
n, k = map(int, input().split())
result = ModInt(1)
fac_tab = [ModInt(1)] * 200000
for i in range(1, len(fac_tab)):
    fac_tab[i] = fac_tab[i - 1] * i

for i in range(2, int(math.sqrt(k) + 1)):
    tmp_cnt = 0
    while k % i == 0:
        k /= i
        tmp_cnt += 1
    result = result * mod_comb(n + tmp_cnt - 1, tmp_cnt)
    # print(result)

if k != 1:
    result = result * n
print(str(result))

Submission status: Accepted

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

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N, M = list(map(int, sys.stdin.buffer.readline().split()))


def get_factors(n):
    """
    素因数分解
    :param int n:
    :rtype: list of int
    """
    if n <= 1:
        return []

    ret = []
    while n > 2 and n % 2 == 0:
        ret.append(2)
        n //= 2
    i = 3
    while i <= math.sqrt(n):
        if n % i == 0:
            ret.append(i)
            n //= i
        else:
            i += 2
    ret.append(n)
    return ret


def mod_inv(a, mod):
    """
    a の逆元
    :param int a:
    :param int mod:
    :return:
    """
    return pow(a, mod - 2, mod)


def ncr(n, r, mod=None):
    """
    scipy.misc.comb または scipy.special.comb と同じ
    組み合わせの数 nCr
    :param int n:
    :param int r:
    :param int mod: 3 以上の素数であること
    :rtype: int
    """
    if n < r:
        return 0

    # 何度も呼ぶ場合は combination.py をつかう
    r = min(n - r, r)
    if r == 0:
        return 1
    if mod:
        return reduce(mul, range(n, n - r, -1)) * mod_inv(reduce(mul, range(r, 0, -1)), mod) % mod
    else:
        # math.factorial よりこっちのが速い
        # https://atcoder.jp/contests/abc110/submissions?f.Task=&f.Language=&f.Status=&f.User=nohtaray
        return reduce(mul, range(n, n - r, -1)) // reduce(mul, range(r, 0, -1))


def nhr(n, r, mod=None):
    """
    重複組み合わせの総数 nHr
    :param int n:
    :param int r:
    :param int mod:
    :return:
    """
    return ncr(n + r - 1, r, mod)


counts = Counter(get_factors(M))
ans = 1
for c in counts.values():
    # N 個から c 個選ぶ重複組合せ
    ans = ans * nhr(N, c, MOD) % MOD
print(ans)

Submission status: Accepted

Solution code:
import sys

mod = 10 ** 9 + 7
sys.setrecursionlimit(mod)

def modpow(a, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        half = modpow(a, p // 2)
        return half * half % mod
    else:
        return a * modpow(a, p - 1) % mod

def combinations(a, b):
    if 2 * b > a:
        return combinations(a, a - b)
    mul = 1
    div = 1
    for i in range(b):
        mul *= (a - i)
        div *= (i + 1)
        mul %= mod
        div %= mod
    return mul * modpow(div, mod - 2) % mod

N, M = map(int, input().split())
i = 2
ans = 1
while i * i <= M:
    if M % i == 0:
        c = 0
        while M % i == 0:
            c += 1
            M /= i
        ans *= combinations(N + c - 1, N - 1)
        ans %= mod
    i += 1

if M != 1:
    ans *= combinations(N + 1 - 1, N - 1)
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
from itertools import groupby
from operator import mul
from functools import reduce

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


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


def main():
    p = [len(list(j)) for i, j in groupby(prime_factorize(M))]
    answer = 1
    for i in p:
        answer *= cmb(i + N - 1, N - 1)
        answer %= mod

    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import groupby

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


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 make_table(n, mod=10 ** 9 + 7):
    N = n
    # 元テーブル
    g1 = [0] * (N + 1)
    g1[0] = 1
    g1[1] = 1

    # 逆元テーブル
    g2 = [0] * (N + 1)
    g2[0] = 1
    g2[1] = 1

    # 逆元テーブル計算用テーブル
    inverse = [0] * (N + 1)
    inverse[0] = 0
    inverse[1] = 1

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

    return g1, g2


def main():
    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

    p = [len(list(j)) for i, j in groupby(prime_factorize(M))]
    g1, g2 = make_table(10 ** 6, mod)
    answer = 1
    for i in p:
        answer *= cmb(i + N - 1, N - 1, mod)
        answer %= mod

    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# ABC 110 D - Factorization
def factorization(n):
    retlist = []
    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
            retlist.append(cnt)

    if temp!=1:
        retlist.append(1)

    if retlist==[]:
        retlist.append(1)

    return retlist

def factorial_mod(n, mod):
    a = 1
    for i in range(1, n + 1):
        a *= i
        a %= mod
    return a
 
def comb_mod(n, k, mod):
    if k > n or k < 0:
        return 0
    fact_n = factorial_mod(n, mod)
    fact_k = factorial_mod(k, mod)
    fact_n_k = factorial_mod(n - k, mod)
    return (fact_n * pow(fact_k, mod - 2, mod) * pow(fact_n_k, mod - 2, mod)) % mod

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

if m==1:
    print(1)
    exit()
f=[]
f=factorization(m)
mod=10**9+7
ans=1
for ff in f:
    t=comb_mod(ff+n-1,ff,mod)
    ans*=t
    ans%=mod
print(ans)

Submission status: Accepted

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

    return arr


def nCr(n,r,mod = 10**9+7):
    r = min(n-r,r)
    numer = denom = 1
    for i in range(1,r+1):
        numer = numer * (n+1-i) %mod
        denom = denom * i % mod
    return numer * pow(denom,mod-2,mod) %mod


n, m = map(int, input().split())
factors = factorization(m)
mod = 10**9 + 7

ans = 1
for factor, count in factors:
    pattern = nCr(count+n-1, count)
    ans *= pattern
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
import sys
import collections


def alg_duplicate_combination_mod(n, r, mod):
    n = n + r - 1
    r = min(n - r, r)
    if r == 0:
        return 1
    else:
        denominator = 1
        for i in range(n, n - r, -1):
            denominator = (denominator * i) % mod
        molecule = 1
        for i in range(1, r + 1):
            molecule = (molecule * i) % mod
        return denominator * pow(molecule, mod - 2, mod) % mod


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, input().rstrip('\n').split()))
    ls = []
    for i in range(2, int(m ** 0.5) + 1):
        while True:
            if m % i == 0:
                ls.append(i)
                m //= i
            else:
                break
    if m != 1:
        ls.append(m)
    t = 1
    ls = collections.Counter(ls)
    for k, v in ls.items():
        t *= alg_duplicate_combination_mod(n, v, mod)
        t %= mod
    print(t)


if __name__ == '__main__':
    solve()