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:
from collections import Counter
import math
mod = 10**9+7
N,M = map(int,input().split())
factors = []
f = 2
while M%f==0:
    M//=2
    factors.append(f)
f = 3
while f*f<=M:
    if M%f==0:
        M//=f
        factors.append(f)
    else:
        f+=2
if M!=1:
    factors.append(M)
count = Counter(factors)

def choose(n,k):
    return math.factorial(n)//(math.factorial(n-k)*math.factorial(k))
ans = 1
for v in count.values():
    ans *= choose(N+v-1,N-1)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()

MOD = 10 ** 9 + 7
N, M = inm()

t = [1]


def fact(x):
    if x >= len(t):
        for i in range(len(t), x + 1):
            t.append(t[-1] * i % MOD)
    return t[x]


def solve():
    k = 2
    m = M
    fs = []
    while k * k <= m:
        cnt = 0
        while m % k == 0:
            m //= k
            cnt += 1
        if cnt:
            fs.append(cnt)
        k += 1
    if m > 1:
        fs.append(1)

    ni = pow(fact(N - 1), MOD - 2, MOD)
    ans = 1
    for c in fs:
        ans = ans * fact(c + N - 1) % MOD
        ans = ans * ni % MOD
        ans = ans * pow(fact(c), MOD - 2, MOD) % MOD
    return ans


print(solve())

Submission status: Accepted

Solution code:
import math
import time

TEST = True
TEST = False


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

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

for i in range(2, 150000):
    fac.append(fac[i-1] * i % MOD)
    inv.append((MOD-inv[MOD%i]*(MOD//i)) % MOD)
    finv.append(finv[i-1]*inv[i]%MOD)


def binom(n, k):
    ans = (fac[n] * finv[n-k]) % MOD
    return (ans * finv[k]) % MOD


ans = 1
y = m
x = 1
while y > 1:
    if x*x > y:
        ans = (ans*binom(n,1)) % MOD
        break
    x += 1
    exp = 0
    while y % x == 0:
        y /= x
        exp += 1
    ans = (ans*binom(exp+n-1, exp)) % MOD
    if TEST:
        print("x = " + str(x) + ", ans = " + str(ans) )

print(ans)

#runTime = time.time() - start
#print("My answer is  " + str(ans))
#print("The running time is " + str(runTime) + " sec")

Submission status: Accepted

Solution code:
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
from scipy.misc import comb
from collections import Counter
n, m = map(int, input().split())
c = Counter(prime_factorize(m))
l = [i[1] for i in c.most_common()]
ans = 1
for i in l:
    ans *= comb(i + n - 1, i, exact=True)
    ans %= 10 ** 9 + 7
print(int(ans))

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def factorization(n):
    factors = []

    if n < 2:
        return n

    while n % 2 == 0:
        factors.append(2)
        n //= 2

    for i in range(3, int(n ** 0.5) + 5, 2):
        while n % i == 0:
            factors.append(i)
            n //= i

    if n != 1:
        factors.append(n)

    return factors


def main():
    from collections import Counter

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

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

    factors = Counter(factorization(m))

    ans = 1

    for cnt in factors.values():
        for i in range(1, cnt + 1):
            ans *= (n + cnt - i)
            ans %= MOD
            ans *= pow(i, MOD - 2, MOD)
            ans %= MOD

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter


def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)


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


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


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

c = Counter(prime_factorize(m))

ans = 1
for v in c.values():
    ans *= combination(v+n-1, n-1)
    ans %= mod

print(ans)

Submission status: Accepted

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

def main():
	K,M = map(int,input().split())
	
	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
	
	N = 10**5+100
	MOD = 10**9+7
	fac = [0]*(N+1)
	fac[0],fac[1] = 1,1
	invfac = [0]*(N+1)
	invfac[0],invfac[1] = 1,1

	for i in range(2,N+1):
		fac[i] = (fac[i-1]*i)%MOD

	invfac[-1] = pow(fac[-1],MOD-2,MOD)
	for i in range(N,0,-1):
		invfac[i-1] = (invfac[i]*i)%MOD

	def coef(x,y):
		num = ((fac[x]*invfac[y])%MOD)*invfac[x-y]%MOD
		return num
	
	fl = factorize(M)
	
	ans = 1
	for pr,cnt in fl:
	    ans *= coef(K+cnt-1,K-1)
	    ans %= MOD
	
	print(ans)
	
if __name__ == "__main__":
	main()

Submission status: Accepted

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

def main():
	K,M = map(int,input().split())
	
	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
	
	N = 10**6
	MOD = 10**9+7
	fac = [0]*(N+1)
	fac[0],fac[1] = 1,1
	invfac = [0]*(N+1)
	invfac[0],invfac[1] = 1,1

	for i in range(2,N+1):
		fac[i] = (fac[i-1]*i)%MOD

	invfac[-1] = pow(fac[-1],MOD-2,MOD)
	for i in range(N,0,-1):
		invfac[i-1] = (invfac[i]*i)%MOD

	def coef(x,y):
		num = ((fac[x]*invfac[y])%MOD)*invfac[x-y]%MOD
		return num
	
	fl = factorize(M)
	
	ans = 1
	for pr,cnt in fl:
	    ans *= coef(K+cnt-1,K-1)
	    ans %= MOD
	
	print(ans)
	
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
# Complexity: O(sqrt(N))

def factor(n):
    res = []
    last = -1
    i = 2
    while i ** 2 <= n:
        while n % i == 0:
            if i != last:
                res.append([i,1])
                last = i
            else:
                res[-1][1] += 1
            n //= i
        i += 1
    if n != 1:
        res.append([n,1])
    return res

# Complexity: O(logN)(pow,floordiv)
# A//B (mod P) is available only if (MOD is prime AND gcd(B,P)==1)

MOD = 10**9+7
class mint:
    def __init__(self, x):
        self.x = x % MOD if isinstance(x, int) else int(x) % MOD
    def __str__(self):
        return str(self.x)
    __repr__ = __str__
    def __iadd__(self, other):
        self.x += other.x if isinstance(other, mint) else other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __isub__(self, other):
        self.x += MOD-other.x if isinstance(other, mint) else MOD-other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __imul__(self, other):
        self.x *= other.x if isinstance(other, mint) else other
        self.x %= MOD
        return self
    def __add__(self, other):
        return (
            mint(self.x + other.x) if isinstance(other, mint) else
            mint(self.x + other)
        )
    def __sub__(self, other):
        return (
            mint(self.x - other.x) if isinstance(other, mint) else
            mint(self.x - other)
        )
    def __mul__(self, other):
        return (
            mint(self.x * other.x) if isinstance(other, mint) else
            mint(self.x * other)
        )
    def __floordiv__(self, other):
        return (
            mint(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(self.x * pow(other, MOD - 2, MOD))
        )
    def __pow__(self, other):
        return (
            mint(pow(self.x, other.x, MOD)) if isinstance(other, mint) else
            mint(pow(self.x, other, MOD))
        )
    __radd__ = __add__
    def __rsub__(self, other):
        return (
            mint(other.x - self.x) if isinstance(other, mint) else
            mint(other - self.x)
        )
    __rmul__ = __mul__
    def __rfloordiv__(self, other):
        return (
            mint(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(other * pow(self.x, MOD - 2, MOD))
        )
    def __rpow__(self, other):
        return (
            mint(pow(other.x, self.x, MOD)) if isinstance(other, mint) else
            mint(pow(other, self.x, MOD))
        )

class Comb():
    # class <mint> should be imported
    def __init__(self, n):
        self.n = n
        fact = [0]*(n+1) # 1-indexed
        ifact = [0]*(n+1) # 逆元
        fact[0] = mint(1)
        for i in range(1, n+1):
            fact[i] = fact[i-1]*i
        ifact[-1] = pow(fact[-1], MOD-2)
        for i in range(n, 0, -1):
            ifact[i-1] = ifact[i]*i
        self.fact = fact
        self.ifact = ifact
    def calc(self, n, k):
        if k<0 or k>n:
            return 0
        return self.fact[n]*self.ifact[k]*self.ifact[n-k]

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

cb=Comb(200005)

f=factor(m)

ans=mint(1)

for p,cnt in f:
    ans*=cb.calc(cnt+n-1,cnt)

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

def factorization(n):
    primen, degree, primend = [], [], []
    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
            primen.append(i)
            degree.append(cnt)
            primend.append([i,cnt])
    if temp!=1:
        primen.append(temp)
        degree.append(1)
        primend.append([temp,1])
    if primen==[]:
        primen.append(n)
        degree.append(1)
        primend.append([n,1])
    return degree
#    return primen,degree


def main():
    N, M = map(int, input().split())
    if M == 1:
        print(1)
    else:
        mod = 10**9+7               # mod素数
        Mf = factorization(M)
        l = max(Mf)
        Comb=[1]*(l+1)
        for i in range(1,l+1):
            tmp = Comb[i-1]
            tmp *= N-1+i
            tmp *= pow(i, mod-2, mod)
            Comb[i] = tmp%mod
        ret = 1
        for i in Mf:
            ret *= Comb[i]
            ret %= mod
        print(ret)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# D - Factorization

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

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

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

for i in range(2, N+36):
    fac.append(fac[-1] * i % MOD)
    inv.append(MOD - inv[MOD%i] * (MOD//i) % MOD)
    finv.append(finv[-1] * inv[-1] % MOD)

def comb_mod(n, r, m):
    if (n<0 or r<0 or n<r): return 0
    r = min(r, n-r)
    return fac[n] * finv[n-r] * finv[r] % m

primes = prime_factorization(M)
ans = 1
if primes != 0:
    for (p, ex) in primes:
        ans = (ans * comb_mod(ex+N-1, N-1, MOD)) % MOD

print(ans)

Submission status: Accepted

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

def pfact(m):
	pf = {}
	for i in range(2,int(m**0.5)+1):
		while m%i==0:
			pf[i]=pf.get(i,0)+1
			m//=i
	if m>1:pf[m]=1
	return pf


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

N = 3 * 10 ** 5  # 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)

#テンプレ終わり

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

factlist = pfact(m).values()

ans = 1

for i in factlist:
	ans = ans * cmb(i+n-1,i,p) % p

print(ans % p)

Submission status: Accepted

Solution code:
from collections import Counter  # N : 素因数分解

MOD = 10**9 + 7


def comb(n, r):
    r = r if n-r <= r else n-r
    a = 1
    for x in list(range(r + 1, n + 1)):
        a *= x % MOD
    b = 1
    for x in list(range(1, n - r + 1)):
        b *= x % MOD
    return (a // b)


N, M = [int(s) for s in input().split()]
prime_factor = []
for i in range(2,int(M**0.5)+1):
    while M%i == 0:
        prime_factor.append(i)
        M/=i
if M > 1:
    prime_factor.append(M)
    
c = Counter(prime_factor)

result = 1

for b in c.values():
    result *= comb(b+N-1, b) % MOD


print(result % MOD)

Submission status: Accepted

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

    a = collections.Counter(a)
    return a

def main():
    N, M = map(int, input().split())
    a = prime_factorize(M)
    mod = 10**9 + 7

    if len(a) == 0:
        print(1)
        return

    ans = 1
    fct = math.factorial
    for i_a in a:
        ans *= (fct(a[i_a]+N-1)//(fct(a[i_a])*fct(N-1))) % mod
        ans %= mod
    print(ans)
    return


if __name__ == "__main__":
    main()
    sys.exit(0)

Submission status: Accepted

Solution code:
import sys, math
from collections import defaultdict
def input(): return sys.stdin.readline().strip()
mod = 10**9+7

class Combination:
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

def factorization(n):
    if n == 1: print("n must be > 1")
    arr = []
    temp = n
    for i in range(2, int(round(n ** 0.5))+1):
        cnt = 0
        while temp % i == 0:
            cnt += 1
            temp //= i
        if cnt > 0: arr.append([i, cnt])
    if temp != 1: arr.append([temp, 1])
    if arr == []: arr.append([n, 1])
    return arr


def main():
    comb = Combination(10**6)
    N, M = map(int, input().split())
    if M == 1:
        print(1)
        return
        
    primes = factorization(M)
    ans = 1
    for _, num in primes:
        ans *= comb(num + (N - 1), num)
        ans %= mod
    print(ans)





if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,m = map(int,ipt().split())
    d = dict()
    mod = 10**9+7
    p = primes(m)
    for i in p:
        t = 0
        while True:
            if m%i == 0:
                m //= i
                t += 1
            else:
                break
        if t > 0:
            d[i] = t
        if i > m:
            break
    if m > 1:
        d[m] = 1
    ans = 1

    #nCrをmodで割った余りを求める。Nに最大値を入れて使用。
    N = 10**5+1000
    g1 = [1, 1] # 元テーブル
    g2 = [1, 1] #逆元テーブル
    inverse = [0, 1] #逆元テーブル計算用テーブル
    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
    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)

    for i in d.values():
        ans = (ans*cmb(n-1+i,i,mod))%mod

    print(ans)

    return

#√nまでの素数の配列を返す関数
def primes(n):
    if n < 4:
        return []
    else:
        pri = [2]
        k = 3
        while k*k <= n:
            for i in pri:
                if k%i == 0:
                    break
                elif i == pri[-1]:
                    pri.append(k)
            k += 2
        return pri

if __name__ == '__main__':
    main()

Submission status: Accepted

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

MOD=10**9+7
n,m=map(int,input().split())
c = Counter(prime_factorize(m))
cv=list(c.values())
ans=1
for i in cv:
    for j in range(i):
        ans*=i+n-1-j
        ans%=MOD
        ans*=pow(1+j,MOD-2,MOD)
        ans%=MOD
print(ans)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,M = LI()

    d = {}
    m = M
    for i in range(2,int(math.sqrt(M))+1):
        while m % i == 0:
            if i in d:
                d[i] += 1
            else:
                d[i] = 1
            m //= i
    if m > 1:
        d[m] = 1

    a = [1]
    b = [1]
    c = 1
    for i in range(1,N+int(math.log(M,2)) +1):
        c = (c * i) % MOD
        a.append(c)
        b.append(pow(c,MOD-2,MOD))

    ans = 1
    for v in d.values():
        ans = (ans * a[N+v-1] * b[v]* b[N-1]) % MOD
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
N,M = map(int,input().split())
primes = []
d = 2
while d**2<=M:
    if M % d == 0:
        M //= d
        primes.append(d)
    else:
        d += 1

if M != 1:
    primes.append(M)

cnt = Counter(primes)

def choose(n,k):
    import math
    return math.factorial(n)//(math.factorial(n-k)*math.factorial(k))
ans = 1
for v in cnt.values():
    ans *= choose(v+(N-1),v)
mod = 10**9 +7
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
mod = 10**9+7
# nCr
def calcComb(n,r):
  mul, div = 1, 1
  for i in range(r):
    mul *= (n-i)
    div *= (i+1)
    mul %= mod
    div %= mod

  return mul * pow(div,mod-2,mod) % mod

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

i = 2
ans = 1
while i*i <= m:
  if m%i == 0:
    cnt = 0
    while m!=1 and m%i == 0:
      cnt += 1
      m //= i
    ans *= calcComb(n+cnt-1, n-1)
    ans %= mod
  i += 1

if m != 1:
  ans *= calcComb(n+1-1, n-1)
  ans %= mod

print(ans)

Submission status: Accepted

Solution code:
import collections,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,M = LI()
ans = 1
def prime_factor(num):
    prime_factor = collections.defaultdict(int)
    for i in range(2,int(num**0.5)+1):
        while num%i==0:
            prime_factor[i] += 1
            num //= i
    if num>1:
        prime_factor[num]=1
    return prime_factor
def nCr(n,r,mod):
    comb_count = 1
    for i in range(r):
        comb_count *= n-i
        comb_count %= mod
    for i in range(1,r+1):
        comb_count *= pow(i,mod-2,mod)
        comb_count %= mod
    return comb_count
for v in prime_factor(M).values():
    ans *= nCr(v+N-1,v,10**9+7)
    ans %= 10**9+7
print(ans)

Submission status: Accepted

Solution code:
import collections,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,M = LI()
ans = 1
def prime_factor(num):
    prime_factor = collections.defaultdict(int)
    for i in range(2,int(num**0.5)+1):
        while num%i==0:
            prime_factor[i] += 1
            num //= i
    if num>1:
        prime_factor[num]=1
    return prime_factor
def nCr(n,r,mod):
    comb_count = 1
    for i in range(r):
        comb_count *= n-i
        comb_count %= mod
    for j in range(1,r+1):
        comb_count *= pow(j,mod-2,mod)
        comb_count %= mod
    return comb_count
for v in prime_factor(M).values():
    ans *= nCr(v+N-1,v,10**9+7)
    ans %= 10**9+7
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
mod = 10**9+7
import collections 
# 素因数分解：Counter型で提出
def is_prime(n):
    ans = []
    for i in range(2,int(n**0.5)+1):
        while not n%i:
            n //= i
            ans.append(i)
    if n !=1:
        ans.append(n)
    return collections.Counter(ans)

#重複組み合わせ
def comb(v):
    ans = 1
    for i in range(1,v+1):
        ans *= N+i-1
        ans *= pow(i,mod-2,mod)
        ans %= mod
    return ans

ans = 1
for v in is_prime(M).values():
    ans *= comb(v)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
#素因数分解して列挙する関数、約数列挙ではない！
from collections import Counter
def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    fct = Counter(fct)
    return fct

mod = 10**9+7
def comb_mod(n,r,mod):
    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

N, M = map(int, input().split())
fact = factorize(M)
ans = 1
for k in fact.values():
    ans *= comb_mod(k+N-1,k,mod)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import collections as col
import math as ma

MOD = 10**9 + 7
def inv(a): return pow(a, MOD-2, MOD)
def comb(n,r,MOD):
    ans = 1
    for i in range(r): # r-i==0でbreak
        ans *= n-i
        ans *= inv(r-i)
        ans %= MOD
    return ans

def prime(n):
    ans = []
    for i in range(2, int(n**0.5)+1):
        while not n%i: n //= i; ans.append(i)
    if n != 1: ans.append(n)
    return ans

n,m = map(int,input().split())
cnt = col.Counter(prime(m))

ans = 1
for key,val in cnt.items():
    #ans *= comb(val + n-1, n-1)
    ans *= comb(val + n-1, n-1, MOD)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
import collections as col
import math as ma

MOD = 10**9 + 7
def inv(a): return pow(a, MOD-2, MOD)
def comb(n,r,MOD):
    ans = ma.factorial(n)%MOD * inv(ma.factorial(r)) * inv(ma.factorial(n-r))
    return ans%MOD

def prime(n):
    ans = []
    for i in range(2, int(n**0.5)+1):
        while not n%i: n //= i; ans.append(i)
    if n != 1: ans.append(n)
    return ans

n,m = map(int,input().split())
cnt = col.Counter(prime(m))

ans = 1
for key,val in cnt.items():
    ans *= comb(val + n-1, n-1, MOD)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
import collections as col
import numpy as np
import math as ma
import scipy.misc as spm #miscellaneous

MOD = 10**9 + 7
def inv(a): return pow(a, MOD-2, MOD)
def comb(n,r):
    ans = ma.factorial(n)%MOD * inv(ma.factorial(r)) * inv(ma.factorial(n-r))
    return ans%MOD

def prime(n):
    ans = []
    for i in range(2, int(n**0.5)+1):
        while not n%i: n //= i; ans.append(i)
    if n != 1: ans.append(n)
    return ans

n,m = map(int,input().split())
cnt = col.Counter(prime(m))

ans = 1
for key,val in cnt.items():
    #ans *= comb(val + n-1, n-1)
    ans *= spm.comb(val + n-1, n-1, exact=1)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,M=map(int,input().split())
    d=defaultdict(int)
    x=2
    while M>1:
        if M%x==0:
            d[x]+=1
            M//=x
        else:
            x+=1
    def COMinit(n,MOD):
        fac,finv,inv=[0]*max(2,n+1),[0]*max(2,n+1),[0]*max(2,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
        return fac,finv,inv
    
    fac,finv,inv=COMinit(10**6,MOD)
    
    def COM(n, k, MOD=MOD):
        if n<k or n<0 or k<0:
            return 0
        return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD
    
    ans=1
    for v in d.values():
        ans*=COM(N-1+v,v,MOD)
        ans%=MOD
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

MOD = 1000000007  # type: int


def solve(N: int, M: int):
    factors = {}
    m = M
    for i in range(2, int(M**0.5)+1):
        while m % i == 0:
            factors[i] = factors.get(i, 0) + 1
            m //= i
    else:
        if m != 1:
            factors[m] = 1
    mf = ModFactorial(MOD)
    ans = 1
    for c in factors.values():
        ans = ans * mf.combination(c+N-1, c) % MOD
    return ans
        

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
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
    print(solve(N, M))

def test():
    import doctest
    doctest.testmod()


def mod_range(mod, start, stop=None, step=1):    
    if stop == None:
        stop = start
        start = 0
    return map(lambda i: i % mod, range(start, stop, step))

def mod_inv(mod, n):
    '''
    >>> mod_inv(3, 2)
    2
    >>> mod_inv(1000000007, 2)
    500000004
    '''
    return pow(n, mod-2, mod)

def mod_permutation(mod, n, r):
    '''
    >>> mod_permutation(1000000007, 10, 2)
    90
    >>> mod_permutation(7, 10, 2)
    6
    '''
    m = 1
    for i in mod_range(mod, n-r+1, n+1):
        m = (m * i) % mod
    return m

def mod_factorial(mod, n):
    '''
    >>> mod_factorial(1000000007, 10)
    3628800
    >>> mod_factorial(7, 6)
    6
    '''
    return mod_permutation(mod, n, n)

def mod_combination(mod, n, r):
    '''
    >>> mod_combination(1000000007, 10, 2)
    45
    >>> mod_combination(7, 10, 2)
    3
    '''
    return mod_permutation(mod, n, r) * mod_inv(mod, mod_factorial(mod, r)) % mod

class ModFactorial:
    def __init__(self, mod, size=1):
        '''
        >>> ModFactorial(7, 7)
        Traceback (most recent call last):
        ...
        AssertionError
        '''
        assert mod > size
        self._mod = mod
        self._init_factorials(size)

    def _mod_range(self, start, stop=None, step=1):
        return mod_range(self._mod, start, stop, step)
    
    def _mod_inv(self, n):
        return mod_inv(self._mod, n)
    
    def _init_factorials(self, size):
        '''
        >>> mf1 = ModFactorial(1000000007)
        >>> mf2 = ModFactorial(1000000007, 10)
        >>> mf1.factorial(10) == mf2.factorial(10)
        True
        '''
        self._factorials = [1] * size        
        n = 1 # リストの参照は遅いので減らす
        for i, m in enumerate(self._mod_range(1, size), 1):
            n = (n * m) % self._mod
            self._factorials[i] = n
            
    def _append_factorials(self, n):
        for m in map(lambda i: i % self._mod, range(len(self._factorials), n+1)):
            self._factorials.append((self._factorials[-1] * m) % self._mod)

    def factorial(self, n):
        '''
        >>> ModFactorial(1000000007).factorial(10)
        3628800
        >>> ModFactorial(7).factorial(6)
        6
        >>> ModFactorial(7).factorial(7)
        Traceback (most recent call last):
        ...
        AssertionError
        '''
        assert n < self._mod
        if len(self._factorials) <= n:
            self._append_factorials(n)
        return self._factorials[n]

    def factorial_inv(self, n):
        '''
        >>> MOD = 1000000007
        >>> mf = ModFactorial(MOD)
        >>> mf.factorial_inv(10)
        283194722
        >>> mf.factorial_inv(10) * mf.factorial(10) % MOD
        1
        >>> MOD = 7
        >>> mf = ModFactorial(MOD)
        >>> mf.factorial_inv(6)
        6
        >>> mf.factorial_inv(6) * mf.factorial(6) % MOD
        1
        '''
        return self._mod_inv(self.factorial(n))

    def permutation(self, n, r):
        '''
        >>> ModFactorial(1000000007).permutation(10, 2)
        90
        '''
        return self.factorial(n) * self.factorial_inv(n-r) % self._mod

    def combination(self, n, r):
        '''
        >>> ModFactorial(1000000007).combination(10, 2)
        45
        '''
        return self.permutation(n, r) * self.factorial_inv(r) % self._mod


if __name__ == '__main__':
    #test()
    main()

Submission status: Accepted

Solution code:
import sys
import math
sys.setrecursionlimit(1000000) # 再帰上限を増やす

def calc_combi(n, m, mod=1000000007):
    """ nCmの組み合わせ数を数える """
    if n - m < m:
        return calc_combi(n, n - m)

    ans_mull, ans_div = 1, 1
    for i in range(m):
        ans_mull *= (n - i)
        ans_div *= (i + 1)
        ans_mull %= mod
        ans_div %= mod
    ans = ans_mull * pow(ans_div, mod - 2, mod) % mod
    return ans

def main():
    input = sys.stdin.readline  # 文字列に対してinputした場合は、rstripするのを忘れずに！
    N, M = map(int, input().rstrip().split())
    mod = 1000000007

    ans = 1
    for i in range(2, math.ceil(math.sqrt(M))):
        if M % i == 0:
            count = 0
            while M % i == 0:
                M /= i
                count += 1
            ans *= calc_combi(count + N - 1, N - 1, mod)
            ans %= mod
    if M != 1:
        ans *= calc_combi(N, 1, mod)
        ans %= mod
    print(ans)

if __name__ == '__main__':
    main()