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:
import sys
from io import StringIO
import unittest
import os

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


# 素因数分解
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 = 10 ** 9 + 7
    ans = 1
    for i in range(r):
        ans *= n - i
        ans %= mod
    for i in range(1, r + 1):
        ans *= pow(i, mod - 2, mod)
        ans %= mod
    return ans


# 実装を行う関数
def resolve(test_def_name=""):
    n, m = map(int, input().split())

    if n == 1 or m == 1:
        print(1)
        return

    # ターゲットを素因数分解
    factor_list = factorization(m)

    ans = 1
    for i in factor_list:
        ans = ans * cmb((n - 1) + i[1], i[1])
        ans = ans % (pow(10, 9) + 7)

    print(ans)


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """2 6"""
        output = """4"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """3 12"""
        output = """18"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """100000 1000000000"""
        output = """957870001"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

MOD = 10 ** 9 + 7
prime_factors = []
i = 2
while i ** 2 <= m:
    ext = 0
    while m % i == 0:
        ext += 1
        m //= i
    if ext:
        prime_factors.append((i, ext))
    i += 1
if m != 1:
    prime_factors.append((m, 1))

ans = 1
for pf, num in prime_factors:
    denominator = 1
    numerator = 1
    for i in range(num):
        denominator *= (i+1)
        numerator *= (num + (n-1)) - i
    ans = (ans * (numerator // denominator)) % MOD
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

MOD = 10 ** 9 + 7
factorial = [0] * (10 ** 6 + 1)
inverse = [0] * (10 ** 6 + 1)
factorial[0] = inverse[0] = 1
for i in range(1, 10 ** 6 + 1):
    factorial[i] = (factorial[i-1] * i) % MOD
    inverse[i] = pow(factorial[i], MOD-2, MOD)

prime_factors = []
total = 0
i = 2
while i ** 2 <= m:
    ext = 0
    while m % i == 0:
        ext += 1
        m //= i
    if ext:
        prime_factors.append((i, ext))
        total += ext
    i += 1
if m != 1:
    prime_factors.append((m, 1))
    total += 1

ans = 1
for pf, num in prime_factors:
    ans = (ans * (factorial[num + (n-1)] * inverse[num] * inverse[n-1])) % MOD
print(ans)

Submission status: Accepted

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

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

arr = factorization(m)
if not arr:
    print(1)
    exit()
ans = 1
for a, b in arr:
    pattern = factorial(b+n-1) // (factorial(b) * factorial(n-1))
    ans = (ans * pattern)%mod

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict


def factorize(n):
    facts = defaultdict(int)
    while n % 2 == 0:
        n //= 2
        facts[2] += 1
    m = 3
    while m * m <= n:
        while n % m == 0:
            facts[m] += 1
            n //= m
        m += 2
    if 1 < n:
        facts[n] += 1
    return facts


MOD = 10 ** 9 + 7  # should be a prime number
MAX = 10 ** 5 + 100
FACTS = [1] * (MAX + 1)
for i in range(1, MAX + 1):
    FACTS[i] = FACTS[i - 1] * i % MOD
FACTINVS = [1] * (MAX + 1)
INVS = [1] * (MAX + 1)
for i in range(2, MAX + 1):
    q, r = divmod(MOD, i)
    INVS[i] = -INVS[r] * q % MOD
    FACTINVS[i] = FACTINVS[i - 1] * INVS[i] % MOD


def nCr(n, r):
    return FACTS[n] * FACTINVS[r] * FACTINVS[n - r]


N, M = map(int, input().split())
factors = factorize(M)
ans = 1
for p, e in factors.items():
    ans = ans * nCr(N - 1 + e, e) % MOD
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
div = []
for i in range(2,int(M**(1/2))+2):
    cur = 0
    while M%i==0:
        M//=i
        cur += 1
    if cur >=1:
        div.append(cur)
if M>1:div.append(1)
div.sort()
mod = 10**9+7
frac = [1]*(N+50)
num=len(frac)
for i in range(num-1):
    frac[i+1] = frac[i]*(i+1)%mod
finv = [1]*(N+50)
finv[-1] = pow(frac[-1],mod-2,mod)
ans = 1
for i in range(1,num):
    finv[num-1-i] = finv[num-i]*(num-i)%mod
for i in div:
    ans  =ans*frac[N+i-1]*finv[N-1]*finv[i]%mod
print(ans)

Submission status: Accepted

Solution code:
import sys
import collections

input = sys.stdin.readline


def modInverse(a, p):
    return pow(a, p - 2, p)


def modBinomial(n, k, p):
    numerator = 1
    for i in range(k):
        numerator = (numerator * (n - i)) % p

    denominator = 1
    for i in range(1, k + 1):
        denominator = (denominator * i) % p

    return (numerator * modInverse(denominator, p)) % p


def main():
    N, M = [int(x) for x in input().split()]

    MOD = 10 ** 9 + 7

    def prime_factorization(n):
        i = 2
        factors = []
        while i * i <= n:
            if n % i:
                i += 1
            else:
                n //= i
                factors.append(i)
        if n > 1:
            factors.append(n)
        return factors

    x = prime_factorization(M)

    c = collections.Counter(x)

    ans = 1
    for k in c.keys():
        ans *= modBinomial(c[k] + N - 1, c[k], MOD)

    print(ans % MOD)


if __name__ == '__main__':
    main()

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([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

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

    return arr

score=factorization(m)
#print(score)

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

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
p = 10**9+7 #割る数
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 計算用
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)

ans=1
for item in score:
    c=item[1]
    ans*=cmb(n+c-1, c, p)
    #print(ans)
print(ans%p)

Submission status: Accepted

Solution code:
from collections import defaultdict
N,M=map(int,input().split())
count=defaultdict(int)
p=2
while p<=10**4.5+5:
    if M%p==0:
        count[p] += 1
        M//=p
    else:
        p+=1
if M>1:
    count[M]+=1
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
ans=1
mod=10**9+7
for i in count.keys():
  ans*=cmb(N-1+count[i],count[i])
  ans%=mod
print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
class mint:
    def __init__(self, i):
        self.i = i
    def __add__(self, m):
        t = self.i + (m.i if isinstance(m, mint) else m)
        if t > MOD:
            t -= MOD
        return mint(t)
    def __radd__(self, m):
        t = self.i + (m.i if isinstance(m, mint) else m)
        if t > MOD:
            t -= MOD
        return mint(t)
    def __mul__(self, m):
        return mint(self.i * (m.i if isinstance(m, mint) else m) % MOD)
    def __sub__(self, m):
        t = self.i - (m.i if isinstance(m, mint) else (m % MOD))
        if t < 0:
            t += MOD
        return mint(t)
    def __pow__(self, m):
        i = self.i
        return mint(pow(i, m, MOD))
    def __truediv__(self, m):
        return mint(self.i * pow(m, MOD - 2, MOD) % MOD)
    def __repr__(self):
        return repr(self.i)

fact_range = 10**6
facts = [1] * (fact_range + 1)
for i in range(0, fact_range):
    facts[i+1] = facts[i] * (i + 1) % MOD

ifacts = [1] * (fact_range + 1)
ifacts[fact_range] = pow(facts[fact_range], MOD - 2, MOD)
for i in range(fact_range, 0, -1):
    ifacts[i-1] = ifacts[i] * i % MOD

def comb(n, k):
    if k < 0 or n < k:
        return 0
    else:
        return facts[n] * ifacts[n-k] % MOD * ifacts[k] % MOD

n, m = map(int, input().split())
d = []
p = 2
while p < 10 ** 5:
    cnt = 0
    while m % p == 0:
        m //= p
        cnt += 1
    if cnt > 0:
        d.append(cnt)
    p += 1
if m > 1:
    d.append(1)
ans = mint(1)
for c in d:
    ans *= comb(n - 1 + c, c)
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


# 60 -> {2:2, 3:1, 5:1}
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():
    com_init()
    n, m = map(int, input().split())
    if m == 1:
        print(1)
        return
        
    fac = factorization(m)
    prime_combs = []
    for prime, cnt in fac.items():
        prime_combs.append(com(n-1+cnt, cnt))

    ans = 1
    for c in prime_combs:
        ans*=c
        ans%=MOD

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 8)
MOD = 10 ** 9 + 7
def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N, M = ZZ()
    MAX_E = 50

    fact = [1] * (N+MAX_E+1) # fact[n] = n!
    ifact = [1] * (N+MAX_E+1)

    for i in range(1, N+MAX_E+1):
        fact[i] = i * fact[i-1]
        fact[i] %= MOD
    ifact[N+MAX_E] = pow(fact[N+MAX_E], MOD-2, MOD)
    for i in range(N+MAX_E)[::-1]: ifact[i] = ((i+1) * ifact[i+1]) % MOD

    def combination(n, r):
        if r < 0 or r > n: return 0
        return (fact[n] * ifact[n-r] * ifact[r]) % MOD

    def prime_factor(num):
        i = 2
        ret = []
        while i*i <= num:
            if num%i != 0:
                i += 1
                continue
            cc = 0
            while num%i == 0:
                num //= i
                cc += 1
            ret.append([i, cc])
            i += 1
        if num != 1: ret.append([num, 1])
        return ret

    ps = prime_factor(M)
    ans = 1
    for p, e in ps:
        ans *= combination(N + e - 1, N - 1)
        ans %= MOD
    print(ans)

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

#素因数分解O(√n)
def primeFactor(n):
    res = defaultdict(lambda: 0)
    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            res[i] += 1
            n = n // i
    if n != 1:
        res[n] = 1
    return res

import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

#重複組み合わせ
def combinations_with_replacement_count(n, r):
    return combinations_count(n + r - 1, r)

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

factors = primeFactor(M)

ans = 1
for v in factors.values():
    ans *= combinations_with_replacement_count(N, v)
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

prime_list = defaultdict(int)
p = 2
while p <= 10**4.5+5:
    if m%p == 0:
        prime_list[p] += 1
        m //= p
    else:
        p += 1

if m > 1:
    prime_list[m] += 1

MOD=10**9+7

def comb(n, r): 
    if r<0 or r>n: 
        return 0
    r=min(r, n-r)
    res=1
    for i in range(r): 
        res=res*(n-i)%MOD*pow(i+1, MOD-2, MOD)%MOD
    return res

ans = 1
for k in prime_list.keys():
    ans *= comb(prime_list[k]+n-1, prime_list[k])
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


class Combination:
    def __init__(self, n: int, mod: int):
        self.mod = mod
        self.fact = [0] * (n + 1)
        self.factinv = [0] * (n + 1)
        self.inv = [0] * (n + 1)
        
        self.fact[0] = self.fact[1] = 1
        self.factinv[0] = self.factinv[1] = 1
        self.inv[1] = 1
        for i in range(2, n + 1):
            self.fact[i] = (self.fact[i - 1] * i) % mod
            self.inv[i] = (-self.inv[mod % i] * (mod // i)) % mod
            self.factinv[i] = (self.factinv[i - 1] * self.inv[i]) % mod
    
    def ncr(self, n: int, r: int):
        if r < 0 or n < r:
            return 0
        r = min(r, n - r)
        return self.fact[n] * self.factinv[r] % self.mod * self.factinv[n - r] % self.mod
    
    def nhr(self, n: int, r: int):
        return self.ncr(n + r - 1, r)
    
    def npr(self, n: int, r: int):
        if r < 0 or n < r:
            return 0
        return self.fact[n] * self.factinv[n - r] % self.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 not arr:
        arr.append([n, 1])
    return arr


def solve():
    N, M = map(int, rl().split())
    MOD = 10 ** 9 + 7
    
    if M == 1:
        print(1)
        return
    
    facts = factorization(M)
    com = Combination(10 ** 5 + 500, MOD)
    
    ans = 1
    for _, exp in facts:
        ans = ans * com.ncr(exp + N - 1, exp) % MOD
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate

def prime_factorization(n):
    res = []
    for i in range(2, int(pow(n, 0.5))+1):
        if n % i: continue
        ex = 0
        while n % i == 0:
            n = n // i
            ex += 1
        res.append((i, ex))
    if n != 1:
        res.append((n, 1))
    return res

def mcomb(n, k, mod):
    def mfac(l, r, mod):
        ans = l
        for i in reversed(range(r, l)):
            ans *= i
            ans %= mod
        return ans

    A = mfac(n, n-k+1, mod)
    B = mfac(k, 1, mod)
    # B = mpow(B,mod-2,mod)
    B = pow(B, mod-2, mod)
    return A * B % mod

def solve():
    N, M = MI()
    fact = prime_factorization(M)
    MOD = 1000000007

    if N == 1:
        print(1)
        return

    ans = 1
    for num, ex in fact:
        ans = ans * mcomb(ex+N-1, N-1, MOD)
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
MOD = 10**9+7

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

primes = [0]
while M % 2 == 0:
    primes[0] += 1
    M //= 2

if M != 1:
    for i in range(3, int(M**0.5+1), 2):
        if M % i == 0:
            primes.append(0)
            while M % i == 0:
                primes[-1] += 1
                M //= i
            if M == 1:
                break
    else:
        primes.append(1)

#combinations[p] = p+N-1 C N-1
combinations = [1]

p_max = max(primes)
for p in range(1, p_max+1):
    combinations.append( combinations[-1] * (p+N-1) * pow(p, MOD-2, MOD) % MOD )

ans = 1
for p in primes:
    ans *= combinations[p]
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
if m==1:
    print(1)
    exit()
def fact(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 find_power(n,mod=10**9+7):
    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,mod=10**9+7):
    powlist=find_power(n)
    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

mod = 10**9+7
NUM = (4*10**5)+100
p_lis=find_power(NUM,mod)
ip_lis=find_inv_power(NUM,mod)

def comb(n,r,mod=10**9+7):
    if n<r:
        return 0
    elif n>=r:
        return (p_lis[n]*ip_lis[r]*ip_lis[n-r])%(mod)

ans=1
for itm in fact(m):
    _, x = itm
    ans*=comb(x+n-1,n-1)
    ans%=mod

print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
div =[]
for i in range(2,int(M**(1/2))+2):
    cur = 0
    while M%i==0:
        M = M//i
        cur += 1
    if cur >=1:
        div.append(cur)
if M>1: div.append(1)
div.sort()
mod = 10**9+7
frac = [1]*(N+50)
num = len(frac)
for i in range(len(frac)-1):
    frac[i+1] = frac[i]*(i+1)%mod
finv = [1] * (N+50)
finv[-1] = pow(frac[-1], mod-2, mod)
for i in range(1, num):
  finv[num-1-i] = finv[num-i] * (num-i) % mod
ans = 1
for i in div:
    ans = ans * frac[N+i-1]*finv[N-1]*finv[i]%mod
print(ans)

Submission status: Accepted

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

Msq = int(M**(1/2)) + 2
yaku = []

for i in range(2, Msq):
  now = 0
  while M%i == 0:
    M = M//i
    now += 1
  if now >= 1:
    yaku.append(now)
    
if M > 1:
  yaku.append(1)
  
yaku.sort()

MOD = 1000000007
frac = [1] * (N+50)
num = len(frac)
for i in range(num-1):
  frac[i+1] = frac[i] * (i+1) % MOD
  
finv = [1] * (N+50)
finv[-1] = pow(frac[-1], MOD-2, MOD)
for i in range(1, num):
  finv[num-1-i] = finv[num-i] * (num-i) % MOD
  
ans = 1
for i in yaku:
  ans = ans * frac[N+i-1] * finv[N-1] * finv[i] % MOD
  
print(ans)

Submission status: Accepted

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

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

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

def cmb1(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 )

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

Submission status: Accepted

Solution code:
def prime_factor(n):
    if n == 1:
        return [[1, 0]]
    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


MOD = 10**9+7
lim = 200000
inv_t = [-1 for i in range(lim+1)]
factrial = [-1 for i in range(lim+1)]
factrial_inv = [-1 for i in range(lim+1)]


def set_inv(max=lim):
    inv_t[0] = 0
    for i in range(1, max):
        inv_t[i] == mod_inv(i)


def mod_inv(x, mod=MOD):
    y, u, v, _x = mod, 1, 0, x
    while y:
        t = _x//y
        _x -= t*y
        _x, y = y, _x
        u -= t*v
        u, v = v, u
    u %= mod
    if u < 0:
        u += mod
    return u


def mod_pow(a, n, mod=MOD):
    res = 1
    while n:
        if n & 1:
            res = res*a % mod
        a = a*a % mod
        n >>= 1
    return res


def set_factrial(max=lim, mod=MOD):
    c = 1
    factrial[0] = factrial_inv[0] = 1
    for i in range(1, max):
        c *= i
        c %= mod
        factrial[i] = c
        factrial_inv[i] = mod_inv(c, mod)


def comb(a, b, mod=MOD):
    if factrial[0] == -1:
        set_factrial()
    return (factrial[a]*factrial_inv[b]*factrial_inv[a-b]) % mod


n, m = [int(_) for _ in input().split()]
ans = 1
for p, e in prime_factor(m):
    ans *= comb(n-1+e, e)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
def prime_factor(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


MOD = 10**9+7
lim = 200000
inv_t = [-1 for i in range(lim+1)]
factrial = [-1 for i in range(lim+1)]
factrial_inv = [-1 for i in range(lim+1)]


def set_inv(max=lim):
    inv_t[0] = 0
    for i in range(1, max):
        inv_t[i] == mod_inv(i)


def mod_inv(x, mod=MOD):
    y, u, v, _x = mod, 1, 0, x
    while y:
        t = _x//y
        _x -= t*y
        _x, y = y, _x
        u -= t*v
        u, v = v, u
    u %= mod
    if u < 0:
        u += mod
    return u


def mod_pow(a, n, mod=MOD):
    res = 1
    while n:
        if n & 1:
            res = res*a % mod
        a = a*a % mod
        n >>= 1
    return res


def set_factrial(max=lim, mod=MOD):
    c = 1
    factrial[0] = factrial_inv[0] = 1
    for i in range(1, max):
        c *= i
        c %= mod
        factrial[i] = c
        factrial_inv[i] = mod_inv(c, mod)


def comb(a, b, mod=MOD):
    if factrial[0] == -1:
        set_factrial()
    return (factrial[a]*factrial_inv[b]*factrial_inv[a-b]) % mod


n, m = [int(_) for _ in input().split()]
ans = 1
for p, e in prime_factor(m):
    ans *= comb(n-1+e, e)
    ans %= MOD
if m==1:
    ans=1
print(ans)

Submission status: Accepted

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

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y // 2) ** 2 % mod
    else            : return power(x, y // 2) ** 2 * x % mod

mod = 10 ** 9 + 7

N = 10 ** 6
factorial = [1]
for i in range(1, N):
    factorial.append(factorial[i - 1] * i % mod)

inverseFactorial = [0] * N
inverseFactorial[N - 1] = power(factorial[N - 1], mod - 2)
for i in range(N - 2, -1, -1):
    inverseFactorial[i] = inverseFactorial[i + 1] * (i + 1) % mod

def comb(x, y):
    return factorial[x] * inverseFactorial[y] * inverseFactorial[x - y] % 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

facts = factorization(m)

if m == 1:
    print(1)
else:
    ans = 1
    for a, b in facts:
        ans *= comb(n+b-1, b)
        ans %= mod
    print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def SI(): return input().split()

def printlist(lst, k='\n'): print(k.join(list(map(str, lst))))
INF = float('inf')

from math import ceil, floor, log2
from collections import deque
from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product
from heapq import heapify, heappop, heappush


def prime_factorization(n):
    res = []
    for i in range(2, int(pow(n, 0.5))+1):
        if n % i: continue
        ex = 0
        while n % i == 0:
            n = n // i
            ex += 1
        res.append((i, ex))
    if n != 1:
        res.append((n, 1))
    return res

def mcomb(n, k, mod):
    def mfac(l, r, mod):
        ans = l
        for i in reversed(range(r, l)):
            ans *= i
            ans %= mod
        return ans

    A = mfac(n,n-k+1,mod)
    B = mfac(k,1,mod)
    # B = mpow(B,mod-2,mod)
    B = pow(B, mod-2, mod)
    return A * B % mod

def solve():
    n, m = MI()
    fact = prime_factorization(m)
    if n == 1:
        print(1)
        return
    # print(fact)
    mod = 1000000007
    ans = 1
    for num, ex in fact:
        # print(ex, mcomb(ex+n-2, n-1, mod))
        ans *= mcomb(ex+n-1, n-1, mod) % mod
    print(ans % mod)


if __name__ == '__main__':
    solve()

Submission status: Accepted

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


def factorization(n):
    if n == 1:
        return []
    arr = []
    temp = n
    global m
    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))
            m = max(m, cnt)

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

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

    return arr


fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]


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


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


A = factorization(M)
ans = 1

for (key, value) in A:
    ans *= cmb(value + N - 1, value)
    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 #出力の制限
N = 10**5+100
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 )
N,M=map(int,input().split())
A=factorization(M)
ans=1
if M==1:
 print(1)
else:
 for i in range(len(A)):
  ans*=cmb(N+A[i][1]-1, N-1, mod)
  ans%=(10**9+7)
 print(ans)

Submission status: Accepted

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

f = [1 for _ in range(10 ** 7)]
f_inv = [1 for _ in range(10 ** 7)]
for i in range(1, 10 ** 6):
    f[i] = f[i-1] * i % mod
    f_inv[i] = pow(f[i], mod-2, mod)

def comb(n, k):
    return f[n] * f_inv[k] * f_inv[n-k] % mod
def factorization(n):
    arr = []
    tmp = n
    for i in range(2, int(n**0.5)+1):
        if tmp % i == 0:
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            arr.append([i, cnt])

    if tmp != 1:
        arr.append([tmp, 1])

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

    return arr

arr = factorization(m)

ans = 1
for _, k in arr:
    ans *= comb(n+k-1, k)
    ans %= mod

print(ans)