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 math
from collections import Counter
n, m = map(int, input().split())

prime_count = 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[int(m)] += 1

if len(prime_count) != 0:
    b_max = max([i for i in prime_count.values()])
else:
    b_max = 1

fac = [1, 1]
finv = [1, 1]
inv = [0, 1]
Mod = 10**9+7
def COMinit():
    #N_C_kのN
    for i in range(2, n+b_max):
        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

ans = 1
COMinit()
for b in prime_count.values():
    ans *= COM(n+b-1, n-1)
    ans %= Mod 

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

N,M = map(int, input().split())
MOD = 10**9+7
# 素因数分解
d = defaultdict(int)
i = 2
while i*i <= M:
    if M % i == 0:
        d[i] += 1
        M //= i
    else:
        i += 1
if M > 1:
    d[M] += 1

# 素因数をN個に分配する方法
def nCr(n,r):
    if n < 0 or r < 0 or n < r: return 0
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n
    
    # 分子のn*(n-1)*...がr個分続くやつ
    numerator = [n-r+k+1 for k in range(r)]
    # 分母：r!=r*(r-1)*...*3*2の要素
    denominator = [k+1 for k in range(r)]
    
    # 分母の要素で割れる部分を割っていく部分
    for p in range(2, r+1):
        # 分母は1,2,3,...rのようになっており、1は意味がないのでスキップした形か
        pivot = denominator[p-1]
        if pivot > 1:
        # 分子のX番目と分母のX-offset番目が共通の約数を持つということだと思う。piv分ずれているのだから、pivの倍数というところか
            offset = (n-r) % p
            for k in range(p-1, r, p):
                # 約分できる要素について割る
                numerator[k - offset]  /= pivot
                denominator[k] /= pivot
            
    ret = 1
    for k in range(r):
        if numerator[k] > 1: ret *= int(numerator[k])
        
    return ret
"""
それぞれの素数についてどの用意分配するか考える
例：2が5個あり、3箇所に分ける（２を受け取らない場所があってもよい）とは
並んでいる５つの２の間にしきりを二つ入れる、のと同じ
なので、5つの２と２つの仕切りの重複順列といえる。
上の例は3H5と表せて、
nHr = (n+r-1)Crとなる
"""
ans = 1
for k in d.keys():
    ans *= nCr((N+d[k]-1), d[k])
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce
from collections import Counter

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_factor(n):
    ass = []
    for i in range(2, int(n ** 0.5) + 1):
        while n  % i == 0:
            ass.append(i)
            n = n // i
    if n != 1:
        ass.append(n)
    return ass

def main():
    N, M = map(int, input().split())
    num_list = prime_factor(M)
    MOD = 10 ** 9 + 7
    C = Counter(num_list)
    ans = 1
    for i, j in C.items():
        ans *= cmb(j+N-1, j)
        ans %= MOD
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import collections


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


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


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
mod=10**9+7
def combination(n, r):
    a = 1
    b = 1
    for i in range(r):
        a *= (n - i)
        b *= (i + 1)
    return a // b
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
d=get_prime_dic(m)
ans=1
for i,j in d.items():
    ans*=combination(n-1+j, j)
    ans%=mod


print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
NUM_MAX = 10**5
is_prime = [True] * NUM_MAX
is_prime[0] = False
is_prime[1] = False
primes = []
for i in range(NUM_MAX):
    if is_prime[i]:
        primes.append(i)
        for j in range(2*i, NUM_MAX, i):
            is_prime[j] = False

def prime_fact(n):
    res = {}
    for p in primes:
        while n % p == 0:
            n //= p
            res[p] = res.get(p, 0) + 1
    if n > 1:
        res[n] = 1
    return res

def inv_pow(a, p):
    res = 1
    while p > 0:
        if p % 2 == 1:
            res = (res * a) % MOD
        p //= 2
        a = (a * a) % MOD
    return res

def comb(n, k):
    p, q = 1, 1
    for i in range(k):
        p = p * (n - i) % MOD
        q = q * (i + 1) % MOD
    return p * inv_pow(q, MOD-2) % MOD

def solve(n, m):
    v = prime_fact(m)
    ans = 1
    for k in v.values():
        ans = ans * comb(n+k-1, k) % MOD
    return ans % MOD

assert solve(2, 6) == 4
assert solve(3, 12) == 18
assert solve(100000, 1000000000) == 957870001

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
def prime_factorize(x):
    a=[]
    b=[]
    while x%2==0:
        if 2 not in b:
            a.append(2)
            b.append(2)
            x/=2
        else:
            a.append(2)
            x/=2
    f=3
    while f*f<=x:
        if x%f==0:
            if f not in b:
              a.append(f)
              b.append(f)
              x/=f
            else:
              a.append(f)
              x/=f
        else:
          f+=2        
    if x!=1:
      a.append(int(x))
      if int(x) not in b:
        b.append(int(x))
    return a,b    

def comb(n, b):
    if b > n - b:
      b = n - b
    r = 1
    for k in range(n, n-b, -1):
      r = r * k
    d = 1
    for k in range(1, b+1):
      d = d * k
    return r // d 
  
ans=1
A,B=prime_factorize(m)

for i in range(len(B)):
  c=A.count(B[i])  
  ans*=comb(c+n-1,c)
  ans%=10**9+7

print(ans)

Submission status: Accepted

Solution code:
import sys
mod = 1000000007

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

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

def div(a, b):
    return mul(a, pow(b, mod-2,mod))

ivl = [0]
def inverse_max(a): #下2つを使用する際の下準備

    now = 1
    for i in range(a):
        i += 1
        now *= i
        now %= mod
        ivl.append(now)

def nCr(n,r):
    return div(ivl[n] , mul(ivl[n-r] , ivl[r]))


N,M = map(int,input().split())
inverse_max(N + 40)

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

l = [2]
now = 3

while now ** 2 <= M:
    flag = True
    for i in l:
        if now % i == 0:
            flag = False
            break
    if flag:
        l.append(now)
    now += 2

dic = {}
for i in l:

    while M % i == 0:
        if i not in dic:
            dic[i] = 1
        else:
            dic[i] += 1

        M //= i

if M != 1:
    dic[M] = 1

ans = 1
#print (dic)

for i in dic:
    ans *= nCr(dic[i] + N - 1,dic[i])
    #print (ans)
    ans %= (10 ** 9 + 7)
print (ans % (10**9+7))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
from collections import  Counter
MOD=10**9+7

def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table

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 = MOD #出力の制限
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 )

tmp=prime_decomposition(m)
df=set(tmp)
df=list(df)
cnt=Counter(tmp)
ans=1

for i in range(len(df)):
    cv=cmb(cnt[df[i]]+n-1,cnt[df[i]],mod)
    ans*=cv%MOD

print(ans%MOD)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect_left
from heapq import heappush, heappop
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()

if M == 1:
	print(1)
	sys.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])
   if temp!=1:
       arr.append([temp, 1])
   if arr==[]:
       arr.append([n, 1])
   return arr

fact_max = 10**6  # 必要そうな階乗の限界を入れる
factorial = [1]
for i in range(1, fact_max):
    factorial.append(factorial[i-1] * i % mod)

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

def C(n, r):
    return (((factorial[n] * x_inv[r]) % mod) * x_inv[n-r]) % mod

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

fact = factorization(M)
ans = 1
for n, power in fact:
	ans = (ans * C(power+N-1, power))%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

DIV=10**9+7

def cmb(n, r, DIV):
  if ( r<0 or r>n ):
    return 0
  r = min(r, n-r)
  return g1[n] * g2[r] * g2[n-r] % DIV

P = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, P + 1 ):
  g1.append( ( g1[-1] * i ) % DIV )
  inverse.append( ( -inverse[DIV % i] * (DIV//i) ) % DIV )
  g2.append( (g2[-1] * inverse[-1]) % DIV )

N,M=map(int,input().split())
if M==1:
  print(1)
  exit(0)
facs=factorization(M)
ans=1
for fac in facs:
  a,b=fac[0],fac[1]
  # 区別しないb個のモノを区別可能なN個の箱に分ける（0個の箱があってもよい）
  # (b+(N+1)) C b
  ans=((ans%DIV)*(cmb(b+(N-1),b,DIV))%DIV)%DIV

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int
def comb(n, k):
    k = min(n-k,k)
    ans = 1
    for i in range(1, k + 1):
        ans = (ans * (n + 1 - i) // i)
    return ans

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 solve(N: int, M: int):
    from collections import Counter
    primes = prime_decomposition(M)

    counter = Counter(primes)
    answer = 1
    for count in counter.values():
        answer *= comb(count+N-1,count)
        answer %= MOD
    
    print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    solve(N, M)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections

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
  
U = 2*10**6
MOD = 10**9+7
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
  fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U],MOD-2,MOD)
 
for i in range(U,0,-1):
  fact_inv[i-1] = (fact_inv[i]*i)%MOD
 
def comb(n,k):
  if k < 0 or k > n:
    return 0
  z = fact[n]
  z *= fact_inv[k]
  z %= MOD
  z *= fact_inv[n-k]
  z %= MOD
  return z

n, m = map(int, input().split())
c = collections.Counter(prime_factorize(m))
ans = 1
for i in c.values():
  ans *= comb(i+n-1, n-1)
  ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
class Factorial:
    def __init__(self, n, mod=10**9+7):
        self.fac = [0] * (n+1)
        self.ifac = [0] * (n+1)
        self.fac[0] = 1
        self.ifac[0] = 1
        modmod = mod - 2
        for i in range(n):
            self.fac[i+1] = self.fac[i] * (i+1) % mod
            self.ifac[i+1] = self.ifac[i] * pow(i+1, modmod, mod) % mod

    def comb(self, n, r):
        if n == 0 and r == 0:
            return 1
        if n < r or n < 0:
            return 0
        tmp =  self.ifac[n-r] * self.ifac[r] % mod
        return tmp * self.fac[n] % mod

    def perm(self, n, r):
        if n == 0 and r == 0:
            return 1
        if n < r or n < 0:
            return 0
        return (self.fac[n] * self.ifac[n-r]) % mod

def make_divisors(n):
    divisors = {}
    tmp = n
    for div in range(2, int(n**0.5)+1):
        if n % div == 0:
            divisors[div] = 0
        while n % div == 0:
            n //= div
            divisors[div] += 1
        div += 1
    if n > 1:
        divisors[n] = 1
    return divisors

n,m = map(int, input().split())
mod = 10**9 + 7
divisors = make_divisors(m)
fact = Factorial(n + sum(divisors.values()) + 1)

ans = 1
for value in divisors.values():
    ans = ans * fact.comb(value+n-1,value) % mod
print(ans)

Submission status: Accepted

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

def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct

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

tup = factorize(M)
snum = 0
ans = 1
for t in tup:
    ans *= nCr(t[1]+N-1,t[1])

print(ans%Mod)

Submission status: Accepted

Solution code:
from collections import defaultdict as dd

N, M = map(int, input().split())
MOD = 10 ** 9 + 7
# a1 x a2 x .. x aN = M となる数列{ai}が何通りあるか
# まずは素因数分解
def make_prime_dict(x):
    primes = dd(int)
    check = 2
    while True:
        if x % check == 0:
            primes[check] += 1
            x = x // check
        else:
            check += 1
            if check > x:
                break
    return dict(primes)

primes = make_prime_dict(M)
if len(primes) == 0:
    print(1)
    exit()
Q = max(primes.values())
fact = [1]
fact_inv = [1]
for i in range(Q+N):
    new_fact = fact[-1] * (i+1) % MOD
    fact.append(new_fact)
    fact_inv.append(pow(new_fact, MOD - 2, MOD))

def mod_comb(n, r, mod):
    return fact[n] * fact_inv[n - r] % mod * fact_inv[r] % mod

res = 1
for q in primes.values():
    res *= mod_comb(q + N - 1, q, MOD)
    res %= MOD

print(res)

Submission status: Accepted

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

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

def combination(n, r, mod=10**9+7):
    n1, r = n+1, min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod
 
c = collections.Counter(primel)

ans = 1
for i in c.values():
    ans *= combination(i+n-1,i)
    ans %= 10**9+7
    
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
mod = 10**9+7
#素因数分解
def factors_nojit(n):
    gaps = [1,2,2,4,2,4,2,4,6,2,6]
    length, cycle = 11, 3
    f, fs, nxt = 2, [], 0
    while f * f <= n:
        while n % f == 0:
            fs.append(f)
            n0 = n
            n //= f
        f += gaps[nxt]
        nxt += 1
        if nxt == length:
            nxt = cycle
    if n > 1: fs.append(n)
    return fs
#Combination事前計算
MAX = 10**5 + 100
fac = [1]*(MAX+1)
for i in range(1,MAX+1):
    fac[i] = (fac[i-1]*i)%mod
rev_m = [1]*(MAX+1)
rev_m[MAX] = pow(fac[MAX],mod-2,mod)
for i in range(MAX,0,-1):
    rev_m[i-1] = (rev_m[i]*i)%mod
def Comb(n,k):#nCk
    return (fac[n]*rev_m[k]*rev_m[n-k])%mod
N,M = map(int, input().split())
fs =  factors_nojit(M)
fs.sort()
dd = defaultdict(int)
ed = []
for f in fs:
    if dd[f] == 0:
        ed.append(f)
    dd[f] += 1
ans =1
for e in ed:
  k = dd[e]
  ans *= Comb(k+N-1,k)
  ans %= mod
print(ans)

Submission status: Accepted

Solution code:
class Combination:
    def __init__(self, size, mod=10**9 + 7):
        self.size = size + 2
        self.mod = mod
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % self.mod
            self.inv[i] = -self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % self.mod

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % self.mod

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % self.mod) % self.mod

    def factN(self, n):
        if n < 0:
            return 0
        return self.fact[n]

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

def primeCount(N):
    R = int(N**(0.5)) + 1  # 素数の範囲
    primes = {}  # 素数のリスト
    n = N
    for num in range(2, R):
        primes[num] = 0
        while n % num == 0:
            n //= num
            primes[num] += 1
    if n > 1 :
        primes[n] = 1
    return { key : val for key, val in primes.items() if val > 0}  # フィルターをかける

primeM = primeCount(M)
ans = 1
comb = Combination(sum(primeM.values()) + N + 100)

for cnt in primeM.values():
    ans *= comb.ncr(cnt + N - 1, cnt)
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy,copy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
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

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def main():
    n, m = MAP()
    if m != 1:
        lis = factorization(m)
        p = 0
        for x in lis:
            p += x[1]
        #print(lis)
        #print(p)

        ans = 1
        for p, b in lis:
            ans *= cmb(b + n - 1, b)

        print(ans%mod)

    else:
        print(1)

if  __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
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

factorial = [1]
for i in range(1, 1000000):
	factorial.append(factorial[i-1] * i % mod)
 
def power(x, y):
	if y == 0:
		return 1
	elif y == 1:
		return x % mod
	elif y % 2 == 0:
		return power(x, int(y/2)) ** 2 % mod
	else:
		return power(x, int((y-1)/2)) ** 2 * x % mod
def C(n, r):
	return (((factorial[n] * x_inv[r]) % mod) * x_inv[n-r]) % mod
 
x_inv = [0] * (1000000)
x_inv[-1] = power(factorial[-1], mod-2)
for i in range(1000000-2, -1, -1):
	x_inv[i] = x_inv[i+1] * (i+1) % mod

N, M = MAP()

fact_M = factorization(M)

ans = 1
if M == 1:
	print(1)
else:
	for n in fact_M:
		ans = (ans*C(n[1]+N-1, n[1]))%mod
	print(ans)

Submission status: Accepted

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

def pow(n,p):
    res=1
    while p >0:
        if p%2==0:
            n = n**2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod

for i in range(1,2*(10**5)):
    fac.append((fac[i-1]*i)%mod)
    caf.append(pow(fac[i],mod-2))

def ncr(n,r):
    if n < r: return 0
    return fac[n]*caf[r]*caf[n-r]

import collections

fl = [1] * 10**5
fl[0] = 0
fl[1] = 0
lprime=[]
for i in range(10**5):
    if fl[i] == 1:
        lprime.append(i)
        ti = i*2
        while ti < n:
            fl[ti] = 0
            ti += i

def prime_factorize(n):
    global lprime
    a = []
    for p in lprime:
        if p * p > n:break
        while n % p == 0:
            a.append(p)
            n //= p
    if n != 1:
        a.append(n)
    return a

tres = prime_factorize(m)
ctres = collections.Counter(tres)
res = 1
for sc in ctres.values():
    res *= ncr(n+sc-1,sc)
    res %= mod
print(res)

Submission status: Accepted

Solution code:
"""
8:30:00
"""

from collections import defaultdict
def getprime(n):
    if not isinstance(n, int):
        raise TypeError("Input int")
    if n < 2:
        raise ValueError("N >= 2")
    prime = []
    # 約数はsqrt(N)まで調べればOK
    data = [i+1 for i in range(1,n)]
    while True:
        p = data[0]
        if p >= int(n**0.5):
            return prime+data
        prime.append(p)
        # pで割り切れないものだけを残す
        data = [d for d in data if d%p != 0]

def factorization(n):
    factors = defaultdict(int)
    primes = getprime(int(n**0.5))
    for prime in primes:
        while n % prime == 0:
            factors[prime] += 1
            n //= prime
            # print(factors,n)
    if n != 1:
        factors[n] += 1
    return factors


def modconb(n,k,mod):
    # テーブルを作る
    fac = [0]*(n+1)
    finv = [0]*(n+1)
    inv = [0]*(n+1)  

    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1

    for i in range(2,n+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

    if n<k: return 0
    if n<0 or k<0: return 0
    return(fac[n]*(finv[k]*finv[n-k]%mod)%mod)

"""
1 * 1 * 1のどこに素因数をかけるか
3^3だとして
どこかで3回3をかけないといけない
a + b + c = 3 //重複組合せ
3*3-1C3
こいつをかけ合わせると答えになる
modconbいる
"""

mod = 10**9 + 7
n, m = map(int, input().split())
if m == 1:
    print(1)
    exit()
factors = factorization(m)
ans = 1
for k in factors.keys():
    x = factors[k]
    ans *= modconb(x+n-1,x,mod)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
MOD = 10**9 + 7

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

Mfact = defaultdict(int)

max_cnt = 1
for i in range(2,int(M**0.5)+1):
    cnt = 0
    while M%i == 0:
        M = M//i
        cnt += 1
    if cnt > 0:
        Mfact[i] = cnt
    max_cnt = max(cnt,max_cnt)
if M > 1:
    Mfact[M] = 1

n = max_cnt + N + 100
fact = [1]*(n+1)
inv = [1]*(n+1)
ifact = [1]*(n+1)
for i in range(1,n+1):
    fact[i] = fact[i-1]*i % MOD
    inv[i] = pow(i,MOD-2,MOD)
    ifact[i] = ifact[i-1]*inv[i] % MOD
def kHr(k,r):
    n = k+r-1
    r = min(r,n-r)
    return (fact[n] * ifact[r] * ifact[n-r]) % MOD

ans = 1
for k,v in Mfact.items():
    ans = (ans * kHr(v+1,N-1)) % MOD
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def modfact(n):
    fact=[1]*(n+1)
    invfact=[1]*(n+1)
    for i in range(1,n+1):
        fact[i]=i*fact[i-1]%MOD
    invfact[n]=pow(fact[n],MOD-2,MOD)
    for i in range(n-1,-1,-1):
        invfact[i]=invfact[i+1]*(i+1)%MOD
    return fact,invfact

def prime_factorization(n):
    assert(n>=2)
    factor=[]
    sqrt=int(n**.5)
    for d in range(2,sqrt+1):
        while(n%d==0):
            n//=d
            factor.append(d)
    if n!=1: factor.append(n)
    return factor

def resolve():
    from collections import Counter
    n,m=map(int,input().split())
    if(m==1):
        print(1)
        return
        
    P=prime_factorization(m)
    C=Counter(P)
    C=list(C.values())

    N=max(C)
    fact,invfact=modfact(N+n)

    ans=1
    for v in C:
        ans*=fact[v+n-1]*invfact[n-1]*invfact[v]
        ans%=MOD
    print(ans)
resolve()

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    # from time import perf_counter
    mod = 10 ** 9 + 7
    n, m = map(int, input().split())

    pow_ = [0] * 31

    # perf = perf_counter()

    x = m
    divisor = 2
    power = 0
    while x % divisor == 0:
        x //= divisor
        power += 1
    if power > 0:
        pow_[power] += 1

    divisor = 3
    while x > 1 and divisor ** 2 <= m:
        power = 0
        while x % divisor == 0:
            x //= divisor
            power += 1
        if power > 0:
            pow_[power] += 1
        divisor += 2
    if x > 1:
        pow_[1] += 1

    # print('prime_factorization', perf_counter() - perf)
    # print(pow_)

    # def prime_factorization(n):
    #     i = 2
    #     res = []
    #     while i * i <= n:
    #         cnt = 0
    #         while n % i == 0:
    #             n /= i
    #             cnt += 1
    #         if cnt > 0:
    #             res.append(cnt)
    #         i += 1
    #     if n > 1:
    #         res.append(1)
    #     return res

    # perf = perf_counter()
    # res = prime_factorization(m)
    # print('prime_factorization', perf_counter() - perf)
    # print(res)

    # perf = perf_counter()

    ans = 1
    t = 1
    d = 1
    for power, cnt in enumerate(pow_[1:], 1):
        # 1 <= power <= 30
        t = t * (n - 1 + power) % mod
        d = d * pow(power, mod - 2, mod) % mod
        # print(power, cnt, ans, t, d)
        ans = ans * pow(t * d % mod, cnt, mod) % mod
        # for _ in range(cnt):
        #     ans = ans * t * d % mod
    print(ans)
    # print('calculation', perf_counter() - perf)

# TLEの原因は、巨大素数の判定
# divisor ** 2 <= m
# で探索を打ち切って、m>1なら巨大な素数
# 冪数をリストにappendする方式の方が数ms速いが、
# 冪数indexに該当素数数を加算していくと
# 最後の計算で、同じ冪数を一括計算できるから、大差ないか

Submission status: Accepted

Solution code:
from math import factorial
from collections import Counter

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

A = prime_factorize(M)
c = Counter(A)
cases = 1

for v in c.values():
    if v > 1:
        x = factorial(v+N-1)%MOD*pow(factorial(N-1)*factorial(v) % MOD, MOD-2, MOD)%MOD
        cases *= x
    else:
        cases *= N
    cases %= MOD
print(cases)

Submission status: Accepted

Solution code:
from math import factorial
from collections import Counter

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

A = prime_factorize(M)
c = Counter(A)
cases = 1

for v in c.values():
    if v > 1:
        x = factorial(v+N-1)*pow(factorial(N-1)*factorial(v) % MOD, MOD-2, MOD)%MOD
        cases *= x
    else:
        cases *= N
    cases %= MOD
print(cases)