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:
# 素因数分解
def prime_decomposition(n):
	i = 2
	table = []
	while i * i <= n:
		while n % i == 0:
			n //= i
			table.append(i)
		i += 1
	if n > 1:
		table.append(n)
	return table

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

# mを法とするaの乗法的逆元
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

# nCr mod m
def combination(n, r, mod=10**9+7):
	r = min(r, n-r)
	res = 1
	for i in range(r):
		res = res * (n - i) * modinv(i+1, mod) % mod
	return res

# nHr mod m
def H(n, r, mod=10**9+7):
	return combination(n+r-1, r, mod)

from collections import defaultdict
N, M = map(int, input().split())
prime_table = prime_decomposition(M)
dic = defaultdict(int) #指数のリスト
for p in prime_table:
    dic[p] += 1

ans=1
for p, b in dic.items():
	ans *= H(N, b, mod=10**9+7)
print(ans%(10**9+7))

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
MOD = 10 ** 9 + 7
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def primeFactorization(n):
    ans = []
    temp = n
    while temp%2 == 0:
        ans.append(2)
        temp //= 2
    for i in range(3, int(n**0.5)+1, 2):
        while temp%i == 0:
            ans.append(i)
            temp //= i
    if temp > 1:
        ans.append(temp)
    return collections.Counter(ans)

def combMod(n, r, p):
    numer = 1
    denom = 1
    for i in range(1, r+1):
        numer = numer * (n-r+i) % p
        denom = denom * i % p
    return numer * pow(denom, p-2, p) % p

def resolve():
    N, M = LI()

    pf = primeFactorization(M)
    # 素因数ごとに、N個のグループにどう振り分けるかを計算する
    ans = 1
    for i in pf.values():
        ans *= combMod(i + N - 1, i, MOD)        
        ans %= MOD

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
MAX = 10**6
MOD = 10**9+7

fac = [0] * (MAX+1)
finv = [0] * (MAX+1)
inv = [0] * (MAX+1)

def comb_init():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX+1):
        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 comb(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD


def prime_factorize(n):
    table = {}
    while n % 2 == 0:
        table[2] = table.get(2, 0) + 1
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            table[f] = table.get(f, 0) + 1
            n //= f
        else:
            f += 2
    if n != 1:
        table[n] = table.get(n, 0) + 1
    return table


if __name__ == '__main__':
    n, m = map(int, input().split())
    comb_init()
    prime_factor = prime_factorize(m)
    res = 1
    for v in prime_factor.values():
        res *= comb(v+n-1, n-1)
        res %= MOD
    print(res)

Submission status: Accepted

Solution code:
from collections import defaultdict
import math
def factorize(n):
    i = 2
    factors = defaultdict(int)
    while i**2 <= n:
        if n % i != 0:
            i += 1
            continue

        while n % i == 0:
            n //= i
            factors[i] += 1
        i += 1

    if n != 1:
        factors[n] += 1

    return factors

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

N, M = map(int, input().split())
factors = factorize(M)
# print(factors)

ans = 1
for key, val in factors.items():
    ans *= C(N + val - 1, val)

MOD = 10**9 + 7
print(ans % MOD)

Submission status: Accepted

Solution code:
from math import floor, sqrt
from collections import defaultdict
N,M = map(int,input().split())
d = defaultdict(int)
for i in range(2, floor(sqrt(M))+1):
    while M % i == 0:
        d[i] += 1
        M //= i
if M != 1:
    d[M] += 1
def comb(n,k):
    if k == 0:
        return 1
    return comb(n-1,k-1) * n // k
ans = 1
for e in d.values():
    ans *= comb(N+e-1, e)
print(ans % (10**9+7))

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
ans = int(M**0.5+10)*[N-1]
mod = 10**9+7
p = 2
O = M

while p<=O**0.5:
  if M%p == 0:
    M = M//p
    ans[p] += 1
  else:
    p+=1
    
if M!=1:
  ans[-1]+=1

out = 1
for r in ans:
  hoge = 1
  for i in range(min(N-1,r-N+1)):
    hoge*=r-i
    hoge//=i+1
  out*=hoge
  out%=mod

print(out)

Submission status: Accepted

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


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
from collections import Counter
L=prime_factorize(M)
c=Counter(L)
k=[]
for v in c.values():
  k.append(v)
mod=10**9+7
P=[1 for i in range(10**6+1)]
for i in range(10**6):
  P[i+1]=P[i]*(i+1)%mod


def comb(a,b):
  return P[a]*pow(P[a-b],mod-2,mod)*pow(P[b],mod-2,mod)%mod
ans=1
for i in range(len(k)):
  ans*=comb(N+k[i]-1,k[i])
  ans%=mod
print(ans)

Submission status: Accepted

Solution code:
import math

# 逆元を利用した組み合わせの計算
#############################################################
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**6

# 元テーブル
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の素因数分解を辞書で返す
#############################################################
def prime_fact(n):
    root = int(math.sqrt(n))
    prime_dict = {}
    for i in range(2, root + 1):
        cnt = 0
        while n % i == 0:
            cnt += 1
            n = n // i
        if cnt:
            prime_dict[i] = cnt
    if n != 1:
        prime_dict[n] = 1
    return prime_dict
#############################################################

N, M = map(int, input().split())
# Mを素因数分解
prime = prime_fact(M)
ans = 1
# Mがある素数pをv個持っていたとする
# a_1, ..., a_N に ちょうどv個を分配する
# v個のボールとN-1本の仕切りの並べ方に相当し、これは (N+v-1)_C_v 通り
for v in prime.values():
    ans *= cmb(N + v - 1, v, mod)
    ans %= mod
print(ans)

Submission status: Accepted

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

nmax = 10**6
mod = 10**9+7
fac = [1]*nmax
finv = [1]*nmax
inv = [1]*nmax
def ncr_pre():
    for i in range(2,nmax):
        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 ncr(n,r):
    if n<r:
        return 0
    if n<0 or r<0:
        return 0
    return fac[n]* (finv[r] * finv[n-r] %mod) %mod

ncr_pre()
n,m = map(int,input().split())
ls = factorize(m)
tmp = 1
for num,cnt in ls:
    if num==1:continue

    tmp=tmp*ncr(n+cnt-1,cnt) %mod
print(tmp)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


# Nの素因数分解を辞書で返す
def prime_fact(n):
    root = int(math.sqrt(n))
    prime_dict = {}
    for i in range(2, root+1):
        cnt = 0
        while n % i == 0:
            cnt += 1
            n = n // i
        if cnt:
            prime_dict[i] = cnt
    if n != 1:
        prime_dict[n] = 1
    return prime_dict


def combination_mod_initialize(n, MOD=10**9+7):
    fac = [1]*(n+1)
    inv = [1]*(n+1)
    for i in range(1, n+1):
        fac[i] = fac[i-1] * i % MOD
        inv[i] = inv[i-1] * pow(i, MOD-2, MOD) % MOD
    return fac, inv

# 二項係数　高速
def combination_mod(n, r, fac, inv, mod=10**9+7):
    return fac[n] * inv[r] * inv[n-r]


def main():
    N, M = NMI()
    PD = prime_fact(M)
    ans = 1
    fac, inv = combination_mod_initialize(10**6, MOD)

    for x in list(PD.values()):
        ans = ans * combination_mod(N+x-1, N-1, fac, inv) % MOD

    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


# Nの素因数分解を辞書で返す
def prime_fact(n):
    root = int(math.sqrt(n))
    prime_dict = {}
    for i in range(2, root+1):
        cnt = 0
        while n % i == 0:
            cnt += 1
            n = n // i
        if cnt:
            prime_dict[i] = cnt
    if n != 1:
        prime_dict[n] = 1
    return prime_dict


def combination_mod_initialize(n, MOD=10**9+7):
    fac = [1]*(n+1)
    inv = [1]*(n+1)
    for i in range(1, n+1):
        fac[i] = fac[i-1] * i % MOD
        inv[i] = inv[i-1] * pow(i, -1, MOD) % MOD
    return fac, inv

# 二項係数　高速
def combination_mod(n, r, fac, inv, mod=10**9+7):
    return fac[n] * inv[r] * inv[n-r]


def main():
    N, M = NMI()
    PD = prime_fact(M)
    ans = 1
    fac, inv = combination_mod_initialize(10**6, MOD)

    for x in list(PD.values()):
        ans = ans * combination_mod(N+x-1, N-1, fac, inv) % MOD

    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

from collections import defaultdict


def prime_factor(n):
    # O(sqrt(N))
    d = defaultdict(int)
    for i in range(2, n + 1):
        if i * i > n:
            break

        while n % i == 0:
            d[i] += 1
            n //= i

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

    return d


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

# Factorial
fac = [0] * (MAX + 1)
fac[0] = 1
fac[1] = 1

# Inverse
inv = [0] * (MAX + 1)
inv[1] = 1

# Inverse factorial
finv = [0] * (MAX + 1)
finv[0] = 1
finv[1] = 1

for i in range(2, MAX + 1):
    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 comb(n, k):
    if n < k or k < 0:
        return 0
    return (fac[n] * finv[k] * finv[n - k]) % MOD


def comb_rep(n, k):
    return comb(n + k - 1, n - 1)


N, M = map(int, input().split())
primes = prime_factor(M)
res = 1
for k in primes.values():
    res *= comb_rep(N, k)
    res %= MOD

print(res)

Submission status: Accepted

Solution code:
def prime_factorization(n):
    """
    nを素因数分解
    :param n:
    :return:素因数分解結果 [(素数S1, count S1),(素数S2, count S2), ...]

    """
    from math import sqrt
    if (n == 0): return []
    if (n == 1): return [(1, 1)]

    res = []
    for i in range(2, int(sqrt(n)) + 1):
        if n == 1: break
        cnt = 0
        while n % i == 0:
            cnt += 1
            n = n // i
        if cnt > 0:
            res.append((i, cnt))
    if n > 1:
        res.append((n, 1))

    return res


class ModFactorial:
    """
    階乗, 組み合わせ, 順列の計算
    """

    def __init__(self, n, MOD=10 ** 9 + 7):
        """

        :param n: 最大の要素数.
        :param MOD:
        """
        kaijo = [0] * (n + 10)
        gyaku = [0] * (n + 10)

        kaijo[0] = 1
        kaijo[1] = 1
        for i in range(2, len(kaijo)):
            kaijo[i] = (i * kaijo[i - 1]) % MOD
        gyaku[0] = 1
        gyaku[1] = 1
        for i in range(2, len(gyaku)):
            gyaku[i] = pow(kaijo[i], MOD - 2, MOD)
        self.kaijo = kaijo
        self.gyaku = gyaku
        self.MOD = MOD

    def nCm(self, n, m):
        return (self.kaijo[n] * self.gyaku[n - m] * self.gyaku[m]) % self.MOD

    def nPm(self, n, m):
        return (self.kaijo[n] * self.gyaku[n - m]) % self.MOD

    def factorial(self, n):
        return self.kaijo[n]


N, M = [int(_) for _ in input().split()]
if M == 1:
    print(1)
    exit()

primes = [v for _, v in prime_factorization(M)]

MOD = 10 ** 9 + 7
mf = ModFactorial(max(primes) + 1 + N, MOD)

ans = 1
for cnt in primes:
    ans = ans * mf.nCm(cnt + N - 1, N - 1)
    ans = ans % MOD
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
MOD = 10**9+7
MAX = 10**6
if M==1:
    print(1)
    exit()
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])
            arr.append(cnt)
    if temp!=1:
        arr.append(1)

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

    return arr

arr = factorization(M)
def COMinit():
    """
    逆元テーブルをつくる前処理
    計算量はO(n)
    1 <= k <= n <= 1e7程度
    p: 素数
    """
    fac = [0]*MAX
    finv = [0]*MAX
    inv = [0]*MAX

    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 1, 1
    inv[0], inv[1] = 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
    return fac, finv, inv


def comb(n, k):
    """
    nCk mod MODを求める.
    この部分はO(1)
    """
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return int(fac[n] * (finv[k] * finv[n-k] % MOD) % MOD)

def perm(n, k):
    """
    nPk mod MOD
    """
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return int((fac[n] * finv[n-k])%MOD)
fac, finv, inv = COMinit()

ans = 1
for k in arr:
    ans *= comb(N+k-1, k)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
import sys
# import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
# from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

def factorization(n):
    prime = []
    num = n
    p = 2
    while p * p <= n:
        cnt = 0
        while num % p == 0:
            cnt += 1
            num //= p
        prime.append((p, cnt))
        p += 1
    if num != 1:
        prime.append((num, 1))
    if not prime:
        prime.append((n, 1))
         
    return prime

def nCr(n, r, mod):
    a, b = 1, 1
    for i in range(r):
        a = a * (n - i) % mod
        b = b * (i + 1) % mod
    
    return a * pow(b, mod - 2, mod) % mod

def Main():
    n, m = read_ints()
    prime = factorization(m)
    ans = 1
    for p, num in prime:
        ans *= nCr(num + n - 1, num, MOD)
        ans %= MOD
    
    if m == 1:
        print(1)
    else:
        print(ans)

if __name__ == '__main__':
    Main()

Submission status: Accepted

Solution code:
# ABC110 D factorization
N,M=map(int,input().split())
p=10**9+7
L=10**5*3
f,inv,finv=[0]*(L+1),[0]*(L+1),[0]*(L+1)

def factorization(N):
    res=[]
    for i in range(2,int(N**(1/2))+2):
        if not N%i:
            r=0
            while not N%i:
                N//=i
                r+=1
            res.append((i,r))
    if N>1:
        res.append((N,1))
    return res

def nCr_init(L,p):
    for i in range(L+1):
        if i<=1:
            f[i],finv[i],inv[i]=1,1,1
        else:
            f[i]=(f[i-1]*i)%p
            inv[i]=(p-inv[p%i]*(p//i))%p
            finv[i]=(finv[i-1]*inv[i])%p

def nCr(n,r,p):
    if 0<=r<=n and 0<=n:
        return (f[n]*finv[n-r]*finv[r])%p
    else:
        return 0

nCr_init(L,p)
p_list=factorization(M)
res=1
for a,r in p_list:
    res=(res*nCr(r+N-1,r,p))%p
print(res)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
if(m==1):
    print(1)
    exit()

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):
            count=0
            while( temp%i == 0):
                count += 1
                temp = temp // i
            arr.append([i, count])

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

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

    return arr

max_n = 2 * 10**5
fac, finv, inv = [0]*max_n, [0]*max_n, [0]*max_n

def comInit(max_n):
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1

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

comInit(max_n)

# 二項係数の計算
def com(n,k):
    if(n < k):
        return 0
    if( (n<0) | (k < 0)):
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

arr = factorization(m)

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

print(ans)

Submission status: Accepted

Solution code:
def factorize(n):
    factor = []
    if n % 2 == 0:
        f = [2, 1]
        n //= 2
        while n % 2 == 0:
            n //= 2
            f[1] += 1
        factor.append(f)
    k = 3
    while k * k <= n:
        if n % k == 0:
            f = [k, 1]
            n //= k
            while n % k == 0:
                n //= k
                f[1] += 1
            factor.append(f)
        k += 2
    if n != 1:
        factor.append([n, 1])
    return factor

def factorial(n, mod):
    fac = [0] * (n + 1)
    inv = [0] * (n + 1)
    fac[0], inv[0] = 1, 1
    for i in range(1, n + 1):
        fac[i] = fac[i-1] * i % mod
        inv[i] = inverse(fac[i], mod)
    return fac, inv

def inverse(a, mod):
    a %= mod # 除数が正なら正になる
    p = mod
    x, y = 0, 1
    while a > 0:
        n = p // a
        p, a = a, p % a, 
        x, y = y, x - n * y
    return x % mod # 除数が正なら正になる

n, m = map(int, input().split())
if m == 1:
    print(1)
    quit()
mod = 10 ** 9 + 7
f = factorize(m)
max_k = max(i for _, i in f)
fac, inv = factorial(n + max_k - 1, mod)
ans = 1
for _, k in f:
    ans = ans * fac[n + k - 1] % mod * inv[n - 1] % mod * inv[k] % 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

from scipy.special import comb
n, m = map(int, input().split())
a = factorization(m)
M = 10**9 + 7

ans = 1
if m == 1:
    print(1)
    exit()
for i in a:
    ans *= comb(n, i[1], exact=True, repetition=True)
    ans = ans%M
print(ans)

Submission status: Accepted

Solution code:
import math
import sys

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

if M == 1:
  print(1)
  sys.exit()
  
limit = math.ceil(math.sqrt(M))
A = []
for i in range(2, limit+1):
  if i in visited:
    continue
  j = i
  while j <= limit:
    visited.add(j)
    j += i
  del j
  k = 0
  while M % i == 0:
    M = M // i
    k += 1
  A.append(k)
if M > 1:
  A.append(1)

  
MOD = 10**9 + 7
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

K = max(A) + N - 1
for i in range(2, K + 1):
    fact.append((fact[-1] * i) % MOD)
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
    factinv.append((factinv[-1] * inv[-1]) % MOD)

# ②事前計算した項を掛け合わせ
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
  
ans = 1  
for a in A:
  ans *= cmb(a + N-1, N-1, MOD)
  ans %= MOD
  
print(ans)
#print(A)

Submission status: Accepted

Solution code:
mod=10**9+7
dic={}
def ADD(x):
	if x in dic:
		dic[x]+=1
	else:
		dic[x]=1
n,m=map(int,input().split())
for i in range(2,int(m**0.5+2)):
	while m%i==0:
		ADD(i)
		m//=i
if m>1:
	ADD(m)
dic=tuple(dic.values())
ans=1
fac=[1]
for i in range(10**6):
	fac.append(fac[-1]*(i+1)%mod)
def c(a,b):
	r=pow(fac[b]*fac[a-b]%mod,mod-2,mod)
	return fac[a]*r%mod
for x in dic:
	ans*=c(x+n-1,x)
	ans%=mod
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

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

    MOD = pow(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_fact_list(n, MOD):
        # make factorial list from 0 to n
        fact = [0] * (n+1)
        inv = [0] * (n+1)
        factinv = [0] * (n+1)

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

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

    def cbn(n, k, MOD, fact = [], factinv = []):
        if len(fact) == 0 and len(factinv) == 0:
            fact, factinv = make_fact_list(n, MOD)
        return fact[n] * factinv[n-k] * factinv[k] % MOD


    d = Counter(prime_factorize(m)).most_common()

    l = d[0][1] + n 

    fact, factinv = make_fact_list(l, MOD)

    a = 1

    for k, v in d:
        a *= cbn(v + n - 1, v, MOD, fact = fact, factinv = factinv) % MOD

    print(a % MOD)

Submission status: Accepted

Solution code:
from collections import Counter

n,m=map(int,input().split())
primes=[]

mod=10**9+7

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


i=2
while i*i<=m:
    if m%i==0:
        while m%i==0:
            primes.append(i)
            m//=i
    
    i+=1
if m>1:
    primes.append(m)

cnt=Counter(primes)

invlst=[1]*(2*10**5)
factlst=[1]*(2*10**5)

for i in range(2,2*10**5):
    invlst[i]=modinv(i)*invlst[i-1]
    factlst[i]=i*factlst[i-1]
    invlst[i]%=mod
    factlst[i]%=mod
ans=1
for v in cnt.values():
    ans*=factlst[v+n-1]*invlst[n-1]*invlst[v]
    ans%=mod

print(ans)

Submission status: Accepted

Solution code:
from math import factorial

N,M=list(map(int, input().split()))
C=10**9+7
def factorization(n):
    if n==1:
        return [[1,1]]
    temp=n
    ans=[]
    for i in range(2, int(n**0.5+1.01)):
        if temp % i ==0:
            ct=0
            while temp % i == 0:
                temp //= i
                ct += 1
            ans.append([i, ct])
    if temp != 1:
        ans.append([temp, 1])
    return ans

L=factorization(M)
# print(L)
# n種類のモノから重複を許してk個選ぶ重複組合せは
# モノk個と仕切りn-1個の順列だから
# (n+k-1)!/k!(n-1)!

ans=1
for i in L:
    if i[0]!=1:
        tmp=(factorial(i[1]+N-1) // (factorial(i[1])*factorial(N-1)))
        # print(tmp)
        ans*=tmp
        ans%=C
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):
  a=1
  b=1
  r = min(r,n-r)
  for i in range(r):
    a = a*(n-i)%mod
    b = b*(i+1)%mod
  return a*pow(b,mod-2,mod)%mod

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

for i,j in f:
  ans *= cmb(j+N-1,j,MOD)
  ans %= MOD
if M == 1:
  ans = 1
print(ans)

Submission status: Accepted

Solution code:
#a module for any prime implication
import random

def primesbelow(N):
    # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    #""" Input N>=6, Returns a list of primes, 2 <= p < N """
    correction = N % 6 > 1
    N = {0:N, 1:N-1, 2:N+4, 3:N+3, 4:N+2, 5:N+1}[N%6]
    sieve = [True] * (N // 3)
    sieve[0] = False
    for i in range(int(N ** .5) // 3 + 1):
        if sieve[i]:
            k = (3 * i + 1) | 1
            sieve[k*k // 3::2*k] = [False] * ((N//6 - (k*k)//6 - 1)//k + 1)
            sieve[(k*k + 4*k - 2*k*(i%2)) // 3::2*k] = [False] * ((N // 6 - (k*k + 4*k - 2*k*(i%2))//6 - 1) // k + 1)
    return [2, 3] + [(3 * i + 1) | 1 for i in range(1, N//3 - correction) if sieve[i]]

smallprimeset = set(primesbelow(100000))
_smallprimeset = 100000
def isprime(n, precision=7):
    # http://en.wikipedia.org/wiki/Miller-Rabin_primality_test#Algorithm_and_running_time
    if n < 1:
        raise ValueError("Out of bounds, first argument must be > 0")
    elif n <= 3:
        return n >= 2
    elif n % 2 == 0:
        return False
    elif n < _smallprimeset:
        return n in smallprimeset


    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1

    for repeat in range(precision):
        a = random.randrange(2, n - 2)
        x = pow(a, d, n)

        if x == 1 or x == n - 1: continue

        for r in range(s - 1):
            x = pow(x, 2, n)
            if x == 1: return False
            if x == n - 1: break
        else: return False

    return True

# https://comeoncodeon.wordpress.com/2010/09/18/pollard-rho-brent-integer-factorization/
def pollard_brent(n):
    if n % 2 == 0: return 2
    if n % 3 == 0: return 3

    y, c, m = random.randint(1, n-1), random.randint(1, n-1), random.randint(1, n-1)
    g, r, q = 1, 1, 1
    while g == 1:
        x = y
        for i in range(r):
            y = (pow(y, 2, n) + c) % n

        k = 0
        while k < r and g==1:
            ys = y
            for i in range(min(m, r-k)):
                y = (pow(y, 2, n) + c) % n
                q = q * abs(x-y) % n
            g = gcd(q, n)
            k += m
        r *= 2
    if g == n:
        while True:
            ys = (pow(ys, 2, n) + c) % n
            g = gcd(abs(x - ys), n)
            if g > 1:
                break

    return g

smallprimes = primesbelow(1000) # might seem low, but 1000*1000 = 1000000, so this will fully factor every composite < 1000000
def primefactors(n, sort=False):
    factors = []

    for checker in smallprimes:
        while n % checker == 0:
            factors.append(checker)
            n //= checker
        if checker > n: break

    if n < 2: return factors

    while n > 1:
        if isprime(n):
            factors.append(n)
            break
        factor = pollard_brent(n) # trial division did not fully factor, switch to pollard-brent
        factors.extend(primefactors(factor)) # recurse to factor the not necessarily prime factor returned by pollard-brent
        n //= factor

    if sort: factors.sort()

    return factors

def factorization(n):
    factors = {}
    for p1 in primefactors(n):
        try:
            factors[p1] += 1
        except KeyError:
            factors[p1] = 1
    return factors

def gcd(a, b):
    if a == b: return a
    while b > 0: a, b = b, a % b
    return a

N=1000000007
def c(n,r):
    a=1
    b=1
    for i in range(n,n-r,-1):
        a=(a*i)%N
    for i in range(1,r+1):
        b=(b*i)%N
    binv=pow(b,N-2,N)
    return (a*binv)%N


n,m=map(int,input().strip().split(" "))
d=factorization(m)
ans=1
for i in d.values():
    ans=(ans*c(i+n-1,n-1))%N

print(ans)

Submission status: Accepted

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


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

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


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

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