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:
# D - Factorization

import math, collections

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

# n以下の全ての素数のセットを返す関数
def prime_set(n):
    primes = set(range(2, n+1))
    for i in range(2, int(n**0.5) + 1):
        primes.difference_update(range(i*2, n+1, i))
    return primes

# nを素因数分解して素因数の全リストを返す関数
def prime_factors_duplicating_list(n):
    f = []
    for i in prime_set(int(n**0.5) + 1):
        while n % i == 0:
            f.append(i)
            n //= i
    if n > 1:
        f.append(n)
    return f

def comb(n, r):
    if n < r:
        return 0
    else:
        tmp, tmp2 = 1, n
        for _ in range(r):
            tmp *= tmp2
            tmp2 -= 1
        return tmp // math.factorial(r)
    
M_pf_dict = collections.Counter(prime_factors_duplicating_list(M))

ans = 1
for value in M_pf_dict.values():
    ans *= comb(N-1+value, value)
    ans %= MOD

print(ans)

Submission status: Accepted

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

def comb(n, r):
    a = 1; b = 1
    for i in range(r):
        a *= (n-i)
        b *= (i+1)
    return a // b 


facts = []

i = 2
m = M
while i * i <= M:
    cnt = 0
    while m % i == 0:
        m //= i
        cnt += 1
    if cnt:
        facts.append(cnt)
    i += 1
if m > 1:
    facts.append(1)
D = 1000000007
res = 1
for f in facts:
    res = (res * comb(f + N - 1, f)) % D 
print(res)

Submission status: Accepted

Solution code:
from collections import Counter
N, M = map(int, input().split())

if M == 1 :
    print(1)

else :
    mod = 10 ** 9 + 7

    fac = [1]
    inv = [1]
    for i in range(1, N + 1) :
        fac.append(fac[-1] * i % mod)
        inv.append(pow(fac[-1], mod - 2, mod))

    def rec(m, pre_divisor, divisors, lev) :
        ret = 0
        if lev == N :
            comb = fac[N]
            for c in Counter(divisors + [m]).values() :
                comb *= inv[c]
                comb %= mod
            ret += comb
            ret %= comb
            return ret
        
        i = pre_divisor
        while i * i <= m :
            if m % i == 0 :
                ret += rec(m // i, i, divisors + [i], lev + 1)
            i += 1
        
        comb = fac[N]
        for c in Counter(divisors + [m]).values() :
            comb *= inv[c]
            comb %= mod
        comb *= inv[N-lev-1]
        comb %= mod
        ret += comb
        ret %= mod
        return ret
        
    print(rec(M, 2, [], 0))

Submission status: Accepted

Solution code:
from math import factorial
MOD = 10**9 + 7

def prime_factor(n):
    res = []
    d = 2
    while d * d <= n:
        if n % d == 0:
            count = 0
            while n % d == 0:
                count += 1
                n = n // d
            res.append(count)
        d += 1
    if n > 1:
        res.append(1)
    return res
    
N, M = map(int, input().split())
ans = 1
for c in prime_factor(M):
    for i in range(c):
        ans *= N + i
    ans = ans // factorial(c)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
mod=10**9+7
def prime_factor(n):
  ass=[]
  for i in range(2,int(n**0.5)+1):
    while n%i==0:ass.append(i);n//=i
  if n!=1:ass.append(n)
  return ass
f=[1]
for i in range(1,200000):f.append(f[-1]*i%mod)
def comb(a,b,m):return f[a]*pow(f[b],m-2,m)*pow(f[a-b],m-2,m)%m

n,m=map(int,input().split())
if m==1:print(1);exit()
d=prime_factor(m)
b=[1]
for i in range(1,len(d)):
  if d[i-1]==d[i]:b[-1]+=1
  else:b.append(1)
ans=1
for i in b:ans*=comb(i+n-1,i,mod);ans%=mod
print(ans)

Submission status: Accepted

Solution code:
# ABC110d
import sys
from collections import Counter
import math
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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


dp = dict()


def combinations_count(n, r):
    if dp.get(n) != None and dp.get(n).get(r) != None:
        return dp[n][r]
    if dp.get(n) == None:
        dp[n] = dict()
    dp[n].update({r: math.factorial(
        n) // (math.factorial(n - r) * math.factorial(r))})
    return dp[n][r]


def combinations_with_replacement_count(n, r):
    return combinations_count(n + r - 1, r)


ans = 1
pr = Counter(prime_factorize(m))
for i in pr.values():
    # print(i)
    t = combinations_count(n + i - 1, i)
    # print(t)
    ans = ans*t % MOD
# print(pr)
# print(len(pr))
print(ans)

Submission status: Accepted

Solution code:

from math import factorial
from operator import mul
from functools import reduce

def comb2(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 pff(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

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


anst = int(1)
for i in L.values():
    anst *= comb2(i+N-1, i)
    anst = anst%1000000007

ans = anst
print(ans)

Submission status: Accepted

Solution code:

def get_prime_dic(n):
    dic = {}

    i = 2
    while i * i <= n:
        while n % i == 0:
            n //= i
            if i in dic:
                dic[i] += 1
            else:
                dic[i] = 1
        i += 1

    if n > 1:
        dic[n] = 1
    return dic
def combination(n, r):
    a = 1
    b = 1
    for i in range(r):
        a *= (n - i)
        b *= (i + 1)
    return a // b


def main():
    N, M = map(int, input().split())
    d = get_prime_dic(M)
    ans = 1
    for k, v in d.items():
        ans *= combination(v + N - 1, v)
        ans %= 1000000007

    print(ans)


main()

Submission status: Accepted

Solution code:
def shave(m):
    m_root = int(m**0.5)
    candidate = [i for i in range(3,m+1,2)]
    for i in range(3,m_root+2,2):
        candidate = [ j for j in candidate if j == i or j % i != 0]   
    candidate = [2] + candidate
    return candidate

def comb(a,b,m):
	if b == 0 or b == a:
		ret = 1
	else:
		ret = 1
		for i in range(a-b+1,a+1):
			ret = (ret * i) % m
		for i in range(1,b+1):
			ret = (ret * pow(i,m-2,m) ) % m
	return ret

mod = 10**9+7
prime_list = shave(int(33333))

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

p_list = []

for i in prime_list:
    if m == 1:
        break
    elif m % i == 0:
        q = 0
        while m % i == 0:
            m //= i
            q += 1
        p_list.append(q)
if m != 1:
    p_list.append(1)

ans = 1
for i in p_list:
    ans *= comb(i+n-1,n-1,mod)
    ans %= mod
print(ans)

Submission status: Accepted

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

n,M=map(int,input().split())
m=10**9+7
 
g1=[1,1]
g2=[1,1]
inverse=[0,1]
 
for i in range(2,n+100):
  g1.append((g1[-1]*i)%m)
  inverse.append((-inverse[m%i]*(m//i))%m)
  g2.append((g2[-1]*inverse[-1])%m)

def primes(n):
  is_prime=[True]*(n+1)
  is_prime[0]=False
  is_prime[1]=False
  for i in range(2,int(n**0.5)+1):
    if not is_prime[i]:
      continue
    for j in range(i*2,n+1,i):
      is_prime[j]=False
  return [i for i in range(n+1) if is_prime[i]]

def fact(n):
  l=primes(int(n**0.5)+1)
  L=[]
  for i in range(len(l)):
    while n%l[i]==0:
      n=n//l[i]
      L.append(l[i])
    if n==1:
      break
  if n!=1:
    L.append(n)
  return L

x=list(collections.Counter(fact(M)).values())
ct=1
for i in range(len(x)):
  ct*=cmb(x[i]+n-1,n-1,m)
  ct%=m
print(ct)

Submission status: Accepted

Solution code:
def fact(n):
    global mod
    if n==0:
        return 1
    else:
        res=1
        for i in range(1,n+1):
            res=(res*i)%mod
        return res

def inv(n):
    global mod
    res=1
    prod=n%mod
    a=mod-2
    while a>0:
        if a%2==1:
            res=(res*prod)%mod
        a//=2
        prod=(prod**2)%mod
    return res

def combi(n,r):
    return (fact(n)*inv(fact(r))*inv(fact(n-r)))%mod

def ord(n,p):
    res=0
    while n%p==0:
        res+=1
        n//=p
    return res

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

if ord(M,2)>0:
    l.append(ord(M,2))
    M//=2**ord(M,2)

p=3
while M>1 and p<=int(10**4.5):
    if ord(M,p)>0:
        l.append(ord(M,p))
        M//=p**ord(M,p)
    p+=2
if M>1:
    l.append(1)
    M=1

ans=1
for e in l:
    ans=(ans*combi(e+N-1,N-1))%mod

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
mod=10**9+7
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

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
lst=prime_factorize(m)
if m!=1:
    li=[1]
else:
    li=[0]
for i in range(1,len(lst)):
    if lst[i]==lst[i-1]:
        li[-1]+=1
    else:
        li.append(1)
ans=1
for u in li:
    a=n-1+u
    x=cmb(a,u)%mod
    ans=(ans*x)%mod
print(ans)

Submission status: Accepted

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

#[[素因数,数]]を出力
def fctr1(n): 
    f=[]
    c=0
    r=int(n**0.5)
    for i in range(2,r+2):
        while n%i==0:
            c+=1
            n=n//i
        if c!=0:
            f.append([i,c])
            c=0
    if n!=1:
        f.append([n,1])
    return f

fact = [1]
fact_inv = [1]
for i in range(10**6):
    new_fact = fact[-1]*(i+1)%mod
    fact.append(new_fact)
    fact_inv.append(pow(new_fact,mod-2,mod))


def mod_comb_k(n,k,mod):
    return fact[n] * fact_inv[k] % mod * fact_inv[n-k] %mod

p = fctr1(m)
res = 1

for e,num in p:
    res = res*mod_comb_k(num+n-1,n-1,mod)%mod

print(res)

Submission status: Accepted

Solution code:
from sys import stdin
from collections import defaultdict

N, M = [int(x) for x in stdin.readline().rstrip().split()]

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

S = defaultdict(int)

i = 2
while i ** 2 <= M:
    while M % i == 0:
        M //= i
        S[i] += 1
    i += 1
if M > 1:
    S[M] += 1

fact = [1]
for k in range(1, 31):
    fact.append(fact[-1] * k)

ans = 1
inf = 10 ** 9 + 7
for x in S:
    tmp = 1
    v = S[x] + N - 1
    for w in range(N, v + 1):
        tmp *= w
    tmp //= fact[S[x]]
    tmp %= inf
    ans *= tmp
    ans %= inf

print(ans)

Submission status: Accepted

Solution code:
def resolve():
    N,M = map(int,input().split())
    import sys
    def modinv(a, mod=10**9+7):
        return pow(a, mod-2, mod)
    def primes(m):
        temp = m
        a = []
        if temp % 2 == 0:
            a.append(1)
            temp //= 2
            while(temp % 2 == 0):
                a[0] += 1
                temp //= 2
        p = 3
        while(p*p < m):
            if temp % p == 0:
                a.append(1)
                temp //= p
                while(temp % p == 0):
                    a[-1] += 1
                    temp //= p
            p += 2
        if temp != 1:
            a.append(1)
        return a
    prime_list = primes(M)
    if prime_list == []:
        print(1)
        sys.exit()
    H = [0 for _ in range(max(prime_list)+1)]
    H[0] = 1
    for k in range(max(prime_list)):
        H[k+1] = (N+k) * H[k] * modinv(k+1) % int(1e9+7)
    ans = 1
    for pr in prime_list: 
        ans *= H[pr]
        ans %= int(1e9+7)
    print(ans)
resolve()

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def factorize(num: int) -> dict:
    """ 素因数分解 """
    from math import sqrt
    from collections import Counter

    d = Counter()
    # 終点はルート切り捨て+1
    for i in range(2, int(sqrt(num))+1):
        # 素因数分解：小さい方から割れるだけ割って素数をカウント
        while num % i == 0:
            num //= i
            d[i] += 1
        # 1まで分解したら終了
        if num == 1:
            break
    # 最後に残ったnumは素数(ただし1^1は1^0なので数に入れない)
    if num != 1:
        d[num] += 1
    return d

class FactInvMOD:
    """ 階乗たくさん使う時用のテーブル準備 """

    def __init__(self, MAX, MOD):
        """ MAX：階乗に使う数値の最大以上まで作る """
        
        MAX += 1
        self.MAX = MAX
        self.MOD = MOD
        # 階乗テーブル
        factorial = [1] * MAX
        factorial[0] = factorial[1] = 1
        for i in range(2, MAX):
            factorial[i] = factorial[i-1] * i % MOD
        # 階乗の逆元テーブル
        inverse = [1] * MAX
        # powに第三引数入れると冪乗のmod付計算を高速にやってくれる
        inverse[MAX-1] = pow(factorial[MAX-1], MOD-2, MOD)
        for i in range(MAX-2, 0, -1):
            # 最後から戻っていくこのループならMAX回powするより処理が速い
            inverse[i] = inverse[i+1] * (i+1) % MOD
        self.fact = factorial
        self.inv = inverse
    
    def nCr(self, n, r):
        """ 組み合わせの数 (必要な階乗と逆元のテーブルを事前に作っておく) """

        if n < r: return 0
        # 10C7 = 10C3
        r = min(r, n-r)
        # 分子の計算
        numerator = self.fact[n]
        # 分母の計算
        denominator = self.inv[r] * self.inv[n-r] % self.MOD
        return numerator * denominator % self.MOD

    def nPr(self, n, r):
        """ 順列 """

        if n < r: return 0
        return self.fact[n] * self.inv[n-r] % self.MOD

    def nHr(self, n, r):
        """ 重複組み合わせ """

        # r個選ぶところにN-1個の仕切りを入れる
        return self.nCr(r+n-1, r)

N, M = MAP()

d = factorize(M)

# 例外処理
if not d:
    print(1)
    exit()

MAX = N + max(d.values())
fim = FactInvMOD(MAX, MOD)
ans = 1
for k, v in d.items():
    ans *= fim.nHr(N, v)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split(' ')))
MOD = int(1e9 + 7)
seeds = []
p = 2
while p*p <= M:
  while M % p == 0:
    seeds.append(p)
    M = M // p
  p += 1
if M > 1:
  seeds.append(M)
 
def comb(n, k):
  ans = 1
  for i in range(1, k + 1):
    ans = (ans * (n + 1 - i) // i)
  return ans
 
ans = 1
hogehoge = set(seeds)
for i in hogehoge:
  a_ct = seeds.count(i)
  ans = (ans * comb(a_ct + N-1, min(a_ct, N-1))) % MOD
print(ans)

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split(' ')))
MOD = int(1e9 + 7)
primes = []
if M % 2 == 0:
  primes.append(2)

seeds = []
p = 2
while M > 1:
  if p*p > M:
    seeds.append(M)
    M = 1
  while M % p == 0:
    seeds.append(p)
    M = M // p
  p += 1

def comb(n, k):
  ans = 1
  for i in range(1, k + 1):
    ans = (ans * (n + 1 - i) // i)
  return ans

ans = 1
hogehoge = set(seeds)
for i in hogehoge:
  a_ct = seeds.count(i)
  ans = (ans * comb(a_ct + N-1, min(a_ct, N-1))) % MOD
print(ans)

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split(' ')))
MOD = int(1e9 + 7)
primes = []
if M % 2 == 0:
  primes.append(2)

seeds = []
p = 2
while M > 1:
  while M % p == 0:
    seeds.append(p)
    M = M // p
  if p*p > M:
    if M != 1:
	    seeds.append(M)
    M = 0
  p += 1

def comb(n, k):
  ans = 1
  for i in range(1, k + 1):
    ans = (ans * (n + 1 - i) // i)
  return ans

ans = 1
hogehoge = set(seeds)
for i in hogehoge:
  a_ct = seeds.count(i)
  ans = (ans * comb(a_ct + N-1, min(a_ct, N-1))) % MOD
print(ans)

Submission status: Accepted

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

def cmb(n, k):
    ret = 1
    for i in range(k):
        ret *=  n - i
        ret //= i + 1
    return ret % mod

primes = [2]
for p in range(3, 1000):
    if all(p % q for q in primes):
        primes.append(p)

ret = 1
for p in primes:
    q = 0
    while m % p == 0:
        m //= p
        q += 1
    if q > 0:
        ret = (ret * cmb(n + q - 1, q)) % mod
if m > 1:
    ret = (ret * cmb(n, 1)) % mod

print(ret)

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce

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

f = factorization(m)
c = 1

for i in range(len(f)):
  c *= cmb(n+f[i][1]-1,f[i][1])%1000000007

if m != 1:
  print(c%1000000007)
else:
  print(1)

Submission status: Accepted

Solution code:
import sys
import math
input = sys.stdin.readline

def factorization(num):
    MAX_PRIME = int(math.sqrt(num)) + 1
    primes = []
    is_prime = [True] * (MAX_PRIME+1)
    for i in range(2, MAX_PRIME+1):
        if is_prime[i]:
            primes.append(i)
            for j in range(2*i, MAX_PRIME+1, i):
                is_prime[j] = False
    insu = []
    tmp = num
    max_count = 0
    for i in range(len(primes)):
        count = 0
        while tmp%primes[i] == 0:
            tmp //= primes[i]
            count += 1
        if count > 0:
            insu.append((primes[i], count))
            max_count = max(max_count, count)
        if tmp == 1:
            break
    if tmp != 1:
        insu.append((tmp, 1))
    return insu, max_count

def main():
    N, M = map(int, input().split())

    MOD = int(1e9) + 7

    insu, max_count = factorization(M)
    
    kai = [1] * (max_count + N)
    for i in range(1, max_count + N):
        kai[i] = (kai[i-1] * i) % MOD
    
    ans = 1
    tmp = pow(kai[N-1], MOD-2, MOD)
    for prime, count in insu:
        ans *= kai[count + N - 1] * tmp * pow(kai[count], MOD-2, MOD)
        ans %= MOD
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def soinsuu(a):
    yy,j=[],2
    y=yy.append
    while(a>1):
        for i in range(j,int(a**0.5)+1):
            if a%i==0:
                y(i)
                a,j=a//i,i
                break
        else:
            y(a)
            break
    yy.sort()
    return yy

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 nCr(n,r,mod=10**9+7):return inv_n(n_func(n-r,mod)*n_func(r,mod)%mod,mod)*n_func(n,mod)%mod


def main():
    mod=10**9+7
    from collections import Counter
    n,m=map(int,input().split())
    s=Counter(soinsuu(m))
    ans=1
    for i in s.values():
        ans=(ans*nCr(n+i-1,i))%mod
    print(ans)
    
if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
N, M = map(int, input().split())
p = dd(int)
mod = 10 ** 9 + 7
maxps = 0
i = 2
while i <= 10 ** 9:
  if M <= 1:
    break
  while M % i == 0:
    p[i] += 1
    maxps = max(maxps, p[i])
    M //= i
  i += 1
if len(p.keys()) == 0 and M > 1:
  p[M] = 1
class Factorial:
  def __init__(self, n, mod):
    self.f=[1]
    for i in range(1, n + 1):
      self.f.append(self.f[-1] * i % mod)
    self.i=[pow(self.f[-1], mod - 2, mod)]
    for i in range(1, n + 1)[: : -1]:
      self.i.append(self.i[-1] * i % mod)
    self.i.reverse()
  def factorial(self, i):
    return self.f[i]
  def ifactorial(self, i):
    return self.i[i]
  def combi(self, n, k):
    return self.f[n] * self.i[n - k] % mod * self.i[k] % mod
res = 1
f = Factorial(maxps + N, mod)
for i in p.keys():
  res *= f.combi(p[i] + N - 1, p[i])
print(res % mod)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a = LI()
    a.sort()
    a, b, c = a
    print(int(str(c)+str(b))+a)
    return

#B
def B():
    _, _, X, Y = LI()
    x = LI()
    y = LI()
    x.append(X)
    y.append(Y)
    x.sort()
    y.sort()
    print("No " * (x[-1] < y[0]) + "War")
    return

#C
def C():
    s = S()
    t = S()
    ds = defaultdict(int)
    dt = defaultdict(int)
    for i in range(len(s)):
        if ds[s[i]]:
            if ds[s[i]] == ord(t[i]):
                continue
            print("No")
            return
        if dt[t[i]]:
            if dt[t[i]] == ord(s[i]):
                continue
            print("No")
            return
        ds[s[i]] = ord(t[i])
        dt[t[i]] = ord(s[i])
    print("Yes")
    return

#D
def D():
    n, m = LI()
    if m == 1:
        print(1)
        return
    def combination_mod(n, k, mod):
        """ powを用いて(nCk) mod p を求める """ 
        """ nCk = n!/((n-k)!k!)を使用 """
        a = factorial[n]
        b = factorial[k] 
        c = factorial[n - k]
        return (a * pow(b, mod - 2, mod) * pow(c, mod - 2, mod)) % mod

    factorial = [None for i in range(200001)]
    factorial[0] = 1
    for i in range(1, 200001):
        factorial[i] = factorial[i - 1] * i
        if factorial[i] >= mod:
            factorial[i] %= mod
    def factorize(n):
        if n < 4:
            return {n:1}
        lis = {}
        i = 2   
        m = n
        while i**2 <= m:
            if m%i == 0:
                lis[i] = 0
                while m%i == 0:
                    m //= i
                    lis[i] += 1
            i += 1
        if m != 1:
            lis[m] = 1
        return lis
    d = factorize(m)
    ans = 1
    for a in d.values():
        ans *= combination_mod(a + n - 1, a, mod)
        if ans >= mod:
            ans %= mod
    print(ans)

    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
from collections import defaultdict

def getlist():
	return list(map(int, input().split()))

const = 10 ** 9 + 7
MAX = 10 ** 5 + 50

#エラトステネス
L = [1 for i in range(100001)]
L[0] = 0
L[1] = 0
plist = []
for i in range(100001):
	if L[i] == 1:
		plist.append(i)
		c = 2
		while True:
			if i * c <= 100000:
				L[i * c] = 0
				c += 1
			else:
				break

#組み合わせ、逆元前計算
fac = [0] * (MAX)
inv = [0] * (MAX)
finv = [0] * (MAX)
fac[0], fac[1] = 1, 1
inv[1] = 1
finv[0], finv[1] = 1, 1

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

#受け取り、処理
N, M = getlist()
if M == 1:
	print(1)
else:
	D = defaultdict(int)
	while M != 1:
		judge = "No"
		for i in plist:
			if M % i == 0:
				D[i] += 1
				M = M // i
				judge = "Yes"
				break
		if judge == "No":
			D[M] += 1
			break

	data = []
	for i in D:
		data.append(D[i])

	#計算
	ans = 1
	for i in data:
		ans *= fac[i + N - 1] * finv[i] * finv[N - 1]
		ans %= const
	print(ans)

Submission status: Accepted

Solution code:
def factorize(n):
    b,e = 2,0
    fct = []
    while b*b <= n:
        while n%b==0:
            n//=b
            e+=1
        if e>0:
            fct.append((b,e))
        b+=1
        e=0
    if n!=1:
        fct.append((n,1))
    return fct
    
N,M = list(map(int,input().split()))
 

if M==1:
    print(1)
else:
    pl = factorize(M)
    
    max_coef=max([p[1] for p in pl])
    
    
    if max_coef==0:
        print(N)
    else:
    
        comb_list = [1]
        c = 1
        mod = 10**9+7
        for i in range(max_coef):
            c *= N+i
            c *= pow(i+1,mod-2,mod)
            c %= mod
            comb_list.append(c)
    
        ans = 1
    
        for p in pl:
            ans*=comb_list[p[1]]
            ans %= mod
    
        print(ans)

Submission status: Accepted

Solution code:
import math

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

MOD = 10 ** 9 + 7

# (a^b)%MODを返す関数
# O(logb)
# 例えばb = 62のとき
# 62 -> 31 -> 30 -> 15 -> 14 -> 7 -> 6 -> 3 -> 2 -> 1 -> 0
def modpow(a, b):
    if b == 0:
        return(1)

    # b:evenのとき
    if b % 2 == 0:
        # a^(b/2)をhalfとしてその二乗を計算
        half_b = b // 2
        half = modpow(a, half_b)
        return((half ** 2) % MOD)
    # b:oddのとき
    else:
        # bを偶数にするために1減らす
        return((a * modpow(a, b-1)) % MOD)

# (aCb)%MODを返す関数
# 例えば10C3のとき
# 10C3 = 10*9*8/3*2*1 = mul/div
def modcomb(a, b):
    # aCb = aC(a-b)なので
    # bが大きかったらa-bに書き換えた方が早い
    if b > a - b:
        return(modcomb(a, a-b))

    # aCb = mul/div
    mul = 1
    div = 1
    for i in range(b):
        mul *= a - i
        div *= b - i
        mul %= MOD
        div %= MOD

    # (mul/div)%MODを求めたい
    # divの逆元を用いる
    # p:primeのときmodpとして(ここではMOD:primeなので使える)
    # a^(-1) ≡　a^(p-2)
    # この式は、ある数をaで割った時のあまりが
    # ある数にa^(p-2)をかけた時のあまりに等しいという意味
    res = (mul * modpow(div, MOD - 2)) % MOD
    return(res)

ans = 1

for i in range(2, math.floor(math.sqrt(M))+1):
    # 次のifがTrueになるiは必然的に素数になる
    if M % i == 0:
        cnt = 0
        while M % i == 0:
            cnt += 1
            M //= i
        ans *= modcomb(cnt + (N - 1), cnt)
        ans %= MOD
# 最後に残った場合、その素数を処理する
if M != 1:
    ans *= modcomb(1 + (N - 1), 1)
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
def factorization(n) -> list:
	if n==1:return [1]
	ret = []
	i = 2
	while i*i<=n:
		while n%i==0:
			n //= i
			ret.append(i)
		i += 1
	if n!=1:ret.append(n)
	return ret
	
from operator import mul
from functools import reduce
def cmb(n,r):
	if n < r:return 0
	r = min(n-r,r)
	if r==0:return 1
	u = reduce(mul, range(n, n-r, -1))
	d = reduce(mul, range(1,r+1))
	return u//d

def main():
	n,m = map(int,input().split())
	mod = 10**9+7
	if m==1:
		print(1)
		exit()
	ans=1
	for v in Counter(factorization(m)).values():
		ans*=cmb(n+v-1,v)
		ans%=mod
	print(ans)
	
if __name__=="__main__":main()

Submission status: Accepted

Solution code:
from collections import Counter
def factorization(n) -> list:
	if n==1:
		return [1]
	ret = []
	i = 2
	while i*i<=n:
		while n%i==0:
			n //= i
			ret.append(i)
		i += 1
	if n!=1:
		ret.append(n)
	return ret

n,m = map(int,input().split())
mod = 10**9+7
if m==1:
	print(1);exit()

factors = Counter(factorization(m))
mx = n+max(factors.values())

fac = [1]*(mx+1)
inv = [1]*(mx+1)
for i in range(1,mx+1):
	fac[i] = fac[i-1] * i % mod
inv[-1] = pow(fac[-1], mod - 2, mod)
for i in range(mx-1, -1, -1):
	inv[i] = inv[i+1] * (i+1) % mod
def cmb(n,r):
	assert n >= r >= 0
	return fac[n] * inv[n-r] * inv[r] % mod
	
ans=1
for v in factors.values():
	ans*=cmb(n+v-1,v)
	ans%=mod

print(ans)

Submission status: Accepted

Solution code:
import collections
import math

MOD = 10**9 + 7


def eratosthenes(n):
    sieve = [True for _ in range(n + 1)]
    sieve[0] = False
    sieve[1] = False

    def _update(p):
        if sieve[p]:
            for i in range(p * 2, n + 1, p):
                sieve[i] = False

    if n > 1:
        _update(2)
    p = 3
    while p * p <= n:
        _update(p)
        p += 2
    return sieve


n, m = map(int, input().split())
mm = math.ceil(math.sqrt(m))
sieve = eratosthenes(mm)
primes = [i for i in range(mm) if sieve[i]]
counter = collections.Counter()
for p in primes:
    while m % p == 0:
        counter[p] += 1
        m //= p
    if m == 1:
        break
else:
    if m != 1:
        counter[m] += 1

me = max(counter.values()) if len(counter.values()) > 0 else 0
factorials = [1]
for i in range(1, me + 1):
    factorials.append(factorials[-1] * i)

res = 1
for p, e in counter.items():
    for i in range(e):
        res *= e + n - 1 - i
    res //= factorials[e]
    res %= MOD
print(res)

Submission status: Accepted

Solution code:
import math
import collections

#Max = 210000
Mod = 1000000007
"""
fac = [0] * Max
finv = [0] * Max
inv = [0] * Max
def COMinit():
    fac[0] = fac[1] = 1
    finv[0] = finv[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 """
fac = [1, 1]
finv = [1, 1]
inv = [0, 1]
def COMinit():
    for i in range(2, N+111):
        fac.append(fac[-1]*i%Mod)
        inv.append((-inv[Mod%i] * (Mod//i)) % Mod)
        finv.append(finv[-1] * inv[-1] % Mod)
    

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

N, M = map(int, input().split())
prime_count = collections.Counter()
for i in range(2, math.ceil(math.sqrt(M))+1):
    while M % i == 0:
        M /= i
        prime_count[i] += 1
if M > 1:
    prime_count[M] += 1

ans = 1
COMinit()
for i, b in prime_count.items():
    tmp = COM(b+N-1, N-1)
    ans = (ans * tmp) % Mod 
print(ans)

Submission status: Accepted

Solution code:
import math
import collections

Mod = 1000000007
fac = [1, 1]
finv = [1, 1]
inv = [0, 1]
def COMinit():
    for i in range(2, N+111):
        fac.append(fac[-1]*i%Mod)
        inv.append((-inv[Mod%i] * (Mod//i)) % Mod)
        finv.append(finv[-1] * inv[-1] % Mod)
    

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

N, M = map(int, input().split())
prime_count = collections.Counter()
for i in range(2, math.ceil(math.sqrt(M))+1):
    while M % i == 0:
        M /= i
        prime_count[i] += 1
if M > 1:
    prime_count[M] += 1

ans = 1
COMinit()
for i, b in prime_count.items():
    tmp = COM(b+N-1, N-1)
    ans = (ans * tmp) % Mod 
print(ans)