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

MAX = 10**5+100
MOD = 10**9+7
fact = [0]*MAX #fact[i]: i!
inv = [0]*MAX #inv[i]: iの逆元
finv = [0]*MAX #finv[i]: i!の逆元
fact[0] = 1
fact[1] = 1
finv[0] = 1
finv[1] = 1
inv[1] = 1
    
for i in range(2, MAX):
    fact[i] = fact[i-1]*i%MOD
    inv[i] = MOD-inv[MOD%i]*(MOD//i)%MOD
    finv[i] = finv[i-1]*inv[i]%MOD

def C(n, r):
    if n<r:
        return 0
    if n<0 or r<0:
        return 0
    return fact[n]*(finv[r]*finv[n-r]%MOD)%MOD

N, M = map(int, input().split())
fct = factorize(M)
ans = 1

for _, c in fct:
    ans *= C(N-1+c, c)
    ans %= MOD

print(ans)

Submission status: Accepted

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

from collections import defaultdict

MOD = 1000000007
fact = []

def main():
    init_fact(2 * 10 ** 5)
    n, m = map(int, input().split())
    pf = prime_factor(m)
    cnt = defaultdict(int)
    for x in pf:
        cnt[x] += 1
    res = 1
    for k, v in cnt.items():
        res *= combi(n - 1 + v, v)
        res %= MOD
    print(res)

def combi(n, k):
    numera = fact[n]
    denomi = (fact[n - k] * fact[k]) % MOD
    return (numera * inv(denomi)) % MOD

def init_fact(maxn):
    assert len(fact) == 0
    fact.append(1)
    for i in range(1, maxn + 1):
        fact.append((fact[i - 1] * i) % MOD)

def inv(n):
    return pow(n, MOD - 2)

def pow(n, p):
    if p == 0:
        return 1
    elif p % 2 == 0:
        x = pow(n, p // 2)
        return (x * x) % MOD
    else:
        x = pow(n, p - 1)
        return (x * n) % MOD

def prime_factor(n):
    # n の素因数を重複有りの昇順リストで返す。O(sqrt n)
    resid = n
    result = []
    i = 2
    while True:
        if resid <= 1:
            return result
        if i ** 2 > resid:
            result.append(resid)
            return result
        if resid % i == 0:
            result.append(i)
            resid //= i
        else:
            i += 1

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
mod = 10**9+7

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

m_p = {}
m_t = m
for i in range(2,math.ceil(m**0.5)+1) :
  if m_t%i == 0:
    m_p[i] = 0
    for j in range(10**9) :
      m_p[i] += 1
      m_t //= i
      if m_t%i != 0 :
        break
if m_t != 1 :
  m_p[m_t] = 1
  
ans = 1
for v in m_p.values() :
  # nCr = c1/c2　とおく
  # n = v+(n-1)
  # r = v
  c1 = 1
  # c1 = (v+n-1)*(v-1+n-1)*...*((v-(v-1))+n-1)の計算
  for i in range(v) :
    c1 = c1*(v-i+n-1)%mod
  # 1/c2 = (1/v)*(1/(v-1))*...*(1/1)の計算
  c2 = 1
  for i in range(v) :
    c2 = c2*pow(v-i,mod-2,mod)%mod
  ans *= c1*c2%mod
  ans %= mod
  
print(ans)

Submission status: Accepted

Solution code:
def main():
    import math
    from collections import Counter

    N,M = map(int,input().split())
    a = []
    def prime_factorize(n):
        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
    prime_factorize(M)
    def combinations_count(n, r):
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
    divisors = Counter(a)
    count = 1
    for k,v in divisors.items():
        count *= combinations_count(v+N-1,v)

    print(count%(10**9+7))
main()

Submission status: Accepted

Solution code:
from collections import defaultdict

def sieve_of_eratosthenes(n):
    sr_n = int(n ** 0.5)
    f = [True] * (sr_n + 1)
    res = []
    for i in range(2, sr_n+1):
        if f[i]:
            res.append(i)
            for j in range(2*i, sr_n+1, i):
                f[j] = False
    return res

def trial_division(n):
    pn = sieve_of_eratosthenes(n)
    res = defaultdict(lambda: 0)
    for p in pn:
        while n % p == 0:
            res[p] += 1
            n //= p
    if n > 1:
        res[n] += 1
    return res

def nCr(n, r):
    r = min(r, n-r)
    fact = 1
    inv = 1
    for i in range(r):
        fact *= (n - i)
        fact %= MOD
        inv *= (i + 1)
        inv %= MOD
    return fact * pow(inv, MOD-2, MOD) % MOD

MOD = 10 ** 9 + 7
N, M = map(int, input().split())
n_pf = trial_division(M).values()
ans = 1
for r in n_pf:
    ans *= nCr(N-1+r, r)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
import math
import sys

def findFactors(n):
    now=n
    f=[]
    while now%2==0:
        now//=2
        f.append(2)
    p=3
    while p<=math.sqrt(n):
        while now%p==0:
            now//=p
            f.append(p)
        p+=2
        if now==1:
            break
    if now>math.sqrt(n):
        f.append(now)
    return f

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

mod=10**9+7
N=10**5+100
g1=[1,1]
g2=[1,1]
inverse=[0,1]

#n!とその逆元を求めておく
for i in range(2,N+1):
    g1.append((g1[-1]*i)%mod)
    inverse.append((-inverse[mod%i]*(mod//i))%mod)
    g2.append((g2[-1]*inverse[-1])%mod)

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

F=findFactors(m)
ans=1

now=F[0]
cnt=0
for f in F:
    if f==now:
        cnt+=1
    else:
        ans*=cmb(n-1+cnt,cnt)
        ans%=mod
        now=f
        cnt=1
ans*=cmb(n-1+cnt,cnt)
ans%=mod
print(ans)

Submission status: Accepted

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

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

m = M
A = []  #Mの素因数のリスト(今回は必要ない)
B = []  #各素因数で何回割り切れるか
for i in range(2,int(math.sqrt(M))+1):
    if m % i == 0:
        A.append(i)
        c = 0
        while m % i == 0:
            m = m // i
            c += 1
        B.append(c)

if m != 1:
    A.append(m)
    B.append(1)

def p(m,n):
    a = 1
    for i in range(n):
        a = a*(m-i) % mod
    return a

def c(m,n):
    return (p(m,n)*pow(p(n,n),mod-2,mod)) % mod

ans = 1
for i in range(len(B)):
    ans = (ans * c(N-1+B[i],B[i])) % mod

print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc110/tasks/abc110_d
# 誤読をしないように気をつけよう
# 発想は惜しいところまで行っていたしもう一回解いてみよう

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


def factorization(n: int):
    if n == 1:
        return []  # 1は素数ではない
    # 素因数分解
    arr = []
    temp = n
    for i in range(2, int(n**0.5) + 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 combination_mod(n, r, mod):
    if r > n:
        return 0  # このような通りの数は無いため便宜上こう定義する
    r = min(r, n - r)
    nf = rf = 1
    for i in range(r):
        nf = nf * (n - i) % mod
        rf = rf * (i + 1) % mod
    return nf * pow(rf, mod - 2, mod) % mod


MOD = 10**9 + 7
facts = factorization(M)
ans = 1
for i, n in facts:
    ans *= combination_mod(n + N - 1, n, MOD)  # 取り出したところがたまたま壁になるっていう発想でもいいかも
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
def factrize(x):
    f = {}
    if x == 1:
        return f
    tmp = x
    i = 2
    while i**2 <= tmp:
        cnt = 0
        while tmp % i == 0:
            cnt += 1
            tmp = tmp//i
        if cnt > 0:
            f[i] = cnt
        i += 1
    if tmp != 1 or f == {}:
        f[tmp] = 1
    return f


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


p = 10**9+7
n, m = map(int, input().split())
A = list(factrize(m).values())
ans = 1
for a in A:
    ans = (ans*comb(a+n-1, a, p)) % p
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
# from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

n,m = myinput()
mod = 10**9 + 7

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

# 素因数分解
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

table = prime_decomposition(m)
# print(table)

# """nを素因数分解"""
# """2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""
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
# print(factorization(m))
## [[2, 3], [3, 1]] 
##  24 = 2^3 * 3^1

# Combinations
def comb_mod_faster(n,k,mod):
    if n<k:
        return 0
    if n<0 or k<0:
        return 0
    k = min(n-k,k)
    ans = 1
    inv = [1]*(k+1)
    if k>=1:
        ans *= (n-k+1)%mod
    for i in range(2,k+1):
        inv[i] = mod - inv[mod%i]*(mod//i)%mod
        ans = ans*(n-k+i)*inv[i]%mod
    return ans

# Repeated Combinations
def repeated_combinations(n,k,mod):
    return comb_mod_faster(n+k-1,k,mod)

f = factorization(m)

ans = 1
for i in range(len(f)):
    k = f[i][1]
    ans *= repeated_combinations(n,k,mod)
print(ans%mod)

Submission status: Accepted

Solution code:
def d_factorization(MOD=10**9 + 7):
    N, M = [int(i) for i in input().split()]

    def prime_factorization_dict(n):
        if n == 1:
            return {2: 0}  # 1は素数の0乗の積とみなす
        i, table = 2, {}
        while i**2 <= n:
            table[i] = 0
            while n % i == 0:
                table[i] += 1
                n //= i
            if table[i] == 0:
                table.pop(i)
            i += 1
        if n > 1:
            table[n] = 1
        return table

    class Combination(object):
        """参考: https://harigami.net/contents?id=5f169f85-5707-4137-87a5-f0068749d9bb"""
        __slots__ = ['mod', 'factorial', 'inverse']

        def __init__(self, max_val_arg: int = 10**6, mod: int = 10**9 + 7):
            fac, inv = [1], []
            fac_append, inv_append = fac.append, inv.append

            for i in range(1, max_val_arg + 1):
                fac_append(fac[-1] * i % mod)

            inv_append(pow(fac[-1], mod - 2, mod))

            for i in range(max_val_arg, 0, -1):
                inv_append((inv[-1] * i) % mod)

            self.mod, self.factorial, self.inverse = mod, fac, inv[::-1]

        def combination(self, n, r):
            if n < 0 or r < 0 or n < r:
                return 0
            return self.factorial[n] * self.inverse[r] * self.inverse[n - r] % self.mod

        def combination_with_repetition(self, n, r):
            return self.combination(n + r - 1, r)

    prime_m = prime_factorization_dict(M)
    h = Combination(max(prime_m.values()) + N - 1).combination_with_repetition
    ans = 1
    for b in prime_m.values():
        ans = (ans * h(N, b)) % MOD
    return ans

print(d_factorization())

Submission status: Accepted

Solution code:
def d_factorization(MOD=10**9 + 7):
    N, M = [int(i) for i in input().split()]

    def prime_factorization_dict(n):
        if n == 1:
            return {2: 0}  # 1は素数の0乗の積とみなす
        i, table = 2, {}
        while i**2 <= n:
            table[i] = 0
            while n % i == 0:
                table[i] += 1
                n //= i
            if table[i] == 0:
                table.pop(i)
            i += 1
        if n > 1:
            table[n] = 1
        return table

    class Combination(object):
        """参考: https://harigami.net/contents?id=5f169f85-5707-4137-87a5-f0068749d9bb"""
        __slots__ = ['mod', 'factorial', 'inverse']

        def __init__(self, max_val_arg: int = 10**6, mod: int = 10**9 + 7):
            fac, inv = [1], []
            fac_append, inv_append = fac.append, inv.append

            for i in range(1, max_val_arg + 1):
                fac_append(fac[-1] * i % mod)

            inv_append(pow(fac[-1], mod - 2, mod))

            for i in range(max_val_arg, 0, -1):
                inv_append((inv[-1] * i) % mod)

            self.mod, self.factorial, self.inverse = mod, fac, inv[::-1]

        def combination(self, n, r):
            if n < 0 or r < 0 or n < r:
                return 0
            return self.factorial[n] * self.inverse[r] * self.inverse[n - r] % self.mod

        def combination_with_repetition(self, n, r):
            if n == 0 and r > 0:
                return 0
            if n >= 0 and r == 0:
                return 1
            return self.combination(n + r - 1, r)

    prime_m = prime_factorization_dict(M)
    h = Combination(max(prime_m.values()) + N - 1).combination_with_repetition
    ans = 1
    for b in prime_m.values():
        ans = (ans * h(N, b)) % MOD
    return ans

print(d_factorization())

Submission status: Accepted

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

N,M = map(int,input().split())
A = list(set(prime_factorize(M)))
List = []
for i in range(len(A)):
    List.append(prime_factorize(M).count(A[i]))
Listans = 1
for i in range(len(List)):
    Listans *= (math.factorial(List[i]+N-1)//(math.factorial(List[i])*math.factorial(N-1)))
print(Listans%(10**9+7))

Submission status: Accepted

Solution code:
def fac(n):
    dic = {}
    cur = n
    for i in range(2,(int(n**0.5)+2)):
        if cur % i == 0:
            count = 0
            while cur % i == 0:
                count += 1
                cur //= i
            dic[i] = count
            if cur == 1:
                break
    if cur != 1:
        dic[cur] = 1
    return dic

def cmb(a,b,c):
    b = min(b,a-b)
    num = 1
    for i in range(b):
        num = num*(a-i) % c
    den = 1
    for i in range(b):
        den = den*(i+1) % c
    return num * pow(den,c-2,c) % c

n,m = map(int,input().split())
mod  = 10**9 + 7
dic = fac(m)
ans = 1
for i in dic.keys():
    x = dic[i]
    ans *= cmb(x+n-1,x,mod)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from math import factorial
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
c = Counter(prime_factorize(m)).values()
def combinations(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))
ans = 1
mod = 10**9 + 7
for i in c:
  ans *= combinations(i+n-1, i)
  ans %= mod
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
arr = []
q = 2
while q*q <= m:
  e = 0
  while m % q == 0:
    e += 1
    m //= q
  if e > 0: arr.append(e)
  q += 1
if m > 1: arr.append(1)
ans = 1
for e in arr:
  comb = 1
  for i in range(e):
    comb = comb * (n+i) // (1+i)
  ans = ans * comb % 1000000007
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    mod = 10**9 + 7

    n,m = map(int, input().split())
    # 素因数分解
    def prime_decomp(n):
        i = 2
        res = []
        while i ** 2 <= n:
            while n % i==0:
                n //= i
                res.append(i)
            i += 1
        if n > 1:
            res.append(n)
        return res
    a = prime_decomp(m)
    c = Counter(a)

    def ncr(n, r, mod):
        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

    res = 1
    for v in c.values():
        res *= ncr(n-1+v, n-1, mod)
    print(res % mod)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def prime_factor(n):
    factors = {}
    if n % 2 == 0:
        cnt = 0
        while n % 2 == 0:
            cnt += 1
            n //= 2
        factors[2] = cnt
    i = 3
    while i * i <= n:
        if n % i == 0:
            cnt = 0
            while n % i == 0:
                cnt += 1
                n //= i
            factors[i] = cnt
        i += 2
    if n != 1:
        factors[n] = 1
    return factors

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

N, M = map(int, input().split())
mod = 10**9+7
ans = 1
for p, e in prime_factor(M).items():
    ans = ans * combination(e + N - 1, e) % mod
print(ans)

Submission status: Accepted

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

import sys
import pprint

sys.setrecursionlimit(10 ** 6)

class Logger:
	def __init__(self, debug):
		self.debug = debug
	def print(self, *args):
		if self.debug:
			pprint.pprint(args)

def prime_fact(n):
	p = {}
	for i in range(2, int(-(-n**0.5//1))+1):
		if n % i == 0:
			while n % i == 0:
				n //= i
				p[i] = p.get(i, 0) + 1
	if n != 1:
		p[n] = p.get(n, 0) + 1
	return p

fact_memo = [1, 1]
def fact(n):
	if len(fact_memo) > n:
		return fact_memo[n]
	else:
		for i in range(len(fact_memo), n+1):
			fact_memo.append(fact_memo[i-1] * i)
		return fact_memo[n]  

def miniComb(n, r):
	a = 1
	for i in range(r):
		a *= n - i
	return a // fact(r)


def main():
	log = Logger(1)
	n, m = map(int, sys.stdin.readline().split())
	p = prime_fact(m)
	ans = 1
	for i in p:
		ans *= miniComb(n + p[i] - 1, p[i])
		ans %= 10 ** 9 + 7
	print(ans)


main()

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from  itertools import permutations

def sieve(n):
    prime = []
    limit = n ** 0.5
    data = [i + 1 for i in range(1,n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e%p != 0]

def Factor(n,primes):
    factor = {}
    for p in primes:
        while n%p == 0:
            n //= p
            if p in factor:
                factor[p] += 1
            else:
                factor[p] = 1
    
    if n != 1:
        factor[n] = 1
    
    return factor

MAXN = 110000
factorial = [1]
for i in range(1, MAXN + 1):
    factorial.append(factorial[-1] * i % MOD)

inv_factorial = [-1] * (MAXN + 1)
inv_factorial[-1] = pow(factorial[-1], MOD-2, MOD)
for i in reversed(range(MAXN)):
    inv_factorial[i] = inv_factorial[i + 1] * (i + 1) % MOD

def fact(n):
    return factorial[n]

def nck(n, k):
    if k>n or k<0:
        return 0
    else:
        return factorial[n] * inv_factorial[n-k] * inv_factorial[k]

def main():
    n,m = map(int,input().split())
    primes = sieve(100000)
    factor = Factor(m,primes)

    ans = 1
    for v in factor.values():
        ans *= nck(v + n - 1,v)
        ans %= MOD
    
    print(ans)

if __name__ =='__main__':
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
mod=10**9+7
N=2*10**5
fac=[1]*(N+3)
inv=[1]*(N+3)
t=1
for i in range(1,N+3):
    t*=i
    t%=mod
    fac[i]=t
t=pow(fac[N+2],mod-2,mod)
for i in range(N+2,0,-1):
    inv[i]=t
    t*=i
    t%=mod
def comb(n,r):
    if r>n or r<0:
        return 0
    return fac[n]*inv[n-r]*inv[r]%mod
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
import collections
c=collections.Counter(prime_factorize(m))
ans=1
for i,j in c.items():
    ans*=comb(n+j-1,j)
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
mod=10**9+7
N=10**5+1+34
p=[1]*N #assume all are primes from start 
for i in range(2,N):
    if p[i]==1:
        for j in range(2*i,N,i):
            p[j]=0
primes=[]
for i in range(2,N):
    if p[i]==1:
        primes.append(i)

#print(primes)
fact=[1]*N
for i in range(2,N):
    fact[i]=(i*fact[i-1])%mod
ifact=[1]*N
ifact[N-1]=pow(fact[N-1],mod-2,mod)
for i in range(N-2,0,-1):
    ifact[i]=((i+1)*ifact[i+1])%mod
ans=1
#print(ifact[:10])
for x in primes:
    if x>m:
        break
    cnt=0
    #print(m,end=' before\n')
    while m%x==0:
        m//=x
        cnt+=1
    if cnt==0:
        continue
#    print(x,cnt)
    #print(m,end=' after\n')
 #   print(fact[n-1+cnt],ifact[cnt],ifact[n-1])
    val=(fact[n-1+cnt]*(ifact[cnt]*ifact[n-1])%mod)%mod
  #  print(val)
    ans=(ans*val)%mod
if m>1:
    ans=(ans*n)%mod
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter, namedtuple, deque

NN = 202020
MOD = 10**9+7
INF = float("inf")

f = [0]*NN
rf = [0]*NN
inv = [0]*NN
f[0], f[1] = 1, 1
rf[0], rf[1] = 1, 1
inv[1] = 1

for i in range(2, NN):
    f[i] = (f[i-1] * i) % MOD
    inv[i] = (-inv[MOD % i] * (MOD // i)) % MOD
    rf[i] = (rf[i-1] * inv[i]) % MOD


def C(n, r):
    return (f[n] * rf[r] * rf[n-r]) % MOD


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())
primes = Counter(prime_factorize(m))


ans = 1
for k, v in primes.items():
    ans = (ans*C(v+n-1, v))%MOD

print(ans)

Submission status: Accepted

Solution code:
from scipy.misc import comb #<-Atcoderではこちらを使うべし


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


ans = 1
n, m = map(int, input().split())
lst = factorization(m)
if lst[0][0] == 1:
    print(1)
    exit()
for e in lst:
    ans *= comb((n + e[1] - 1), n - 1, exact=True)
print(ans % 1000000007)

Submission status: Accepted

Solution code:
def resolve():
    n,m= map(int, input().split())
    a=[]
    b=[]
    i=2
    l=1
    while m!=1:
      while m%i!=0:
        i+=1
      a.append(i)
      m=m//i
    au=list(set(a))
    for j in range(len(au)):
        b.append(a.count(au[j]))
    from operator import mul
    from functools import reduce

    def cmb(n, r):
        r = min(n - r, r)
        if r == 0: return 1
        over = reduce(mul, range(n, n - r, -1))
        under = reduce(mul, range(1, r + 1))
        return over // under

    for k in b:
        l*=cmb(k+n-1,n-1)

    print(l%(10**9+7))
resolve()

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

def ncr(n, r, p):
    num = den = 1
    for i in range(r):
        num = (num * (n - i)) % p
        den = (den * (i + 1)) % p
    return (num * pow(den, p - 2, p)) % p
p=10**9+7 

ans = 1
for k, v in prime_count.items():
    ans *= ncr(v+n-1, v, p)
    ans %= p

print(ans)

Submission status: Accepted

Solution code:
mod = 10**9+7
def prime(n,p):
    iteral = 0
    while n%p == 0:
        n //= p
        iteral += 1
    return iteral,n
def modpow(a,n):#二乗
    if n==0:
        return 1
    elif n==1:
        return a%mod
    elif n%2==0:
        return (modpow(a,n/2)**2)%mod
    else:
        return (a*modpow(a,n-1))%mod
def modfact(l,r):#階乗
    fact=1
    for i in range(l-r+1):
        fact=fact*(r+i)%mod
    return fact
def comb(n,x):#組み合わせ
    S=modfact(n,n-x+1)
    fact=modfact(x,1)
    T=modpow(fact,mod-2)
    return S*T%mod

def sieve(N):#エラトステネスの篩
    prime = [0]*(N+1)
    isprime = [True]*(N+1)
    isprime[0]=isprime[1] = False
    num = 0
    for p in range(2,N+1):
        if isprime[p]:
            prime[num] = p
            num += 1
            for j in range(2*p,N+1,p):
                isprime[j] = False
    prime.sort()
    prime.reverse()
    for k in range(N-1):
        if prime[k+1] == 0:
            end = k
            break
    return prime[:end+1]
def main():
    N,M = map(int,input().split())
    b = {}
    for i in reversed(sieve(int(M**0.5)+10)):
        if M%i==0:
            num,M = prime(M,i)
            b[i] = num
    if M > 1:
        b[M] = 1
    ans = 1
    for num in b:
        ans *= comb(b[num]+N-1,b[num])
        ans %= mod
    print(ans)

if __name__ == "__main__":
    main()

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):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 2*10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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



n,m=map(int,input().split())
if m==1:
  print(1)
  exit()
A=factorization(m)
ans=1
for i in range(len(A)):
  ans=ans*cmb(n+A[i][1]-1,A[i][1])%mod
print(ans)

Submission status: Accepted

Solution code:
import sys
n,m=map(int,input().split())
MOD = 10**9+7
ans=1
if m==1:
  print(1)
  sys.exit()
def inv_mod(a, p=MOD):
    def inv_mod_sub(a, p):
        if a == 1:
            return 1, 0
        else:
            d, r = p//a, p%a
            x, y = inv_mod_sub(r, a)
            return y-d*x, x
    if p < 0: p = -p
    a %= p
    return inv_mod_sub(a,p)[0] % p

def comb_mod(n, k):
    if k < 0 or k > n:
        return 0
    else:
        return f_mod[n]*f_mod_inverse[k]*f_mod_inverse[n-k] % MOD
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
Max=max(list(pf.values()))
f_mod=[1]*(Max+n+1)
f_mod_inverse=[1]*(Max+n+1)
for i in range(1,Max+n+1):
  f_mod[i]=(f_mod[i-1]*i)%MOD
  f_mod_inverse[i]=(f_mod_inverse[i-1]*inv_mod(i)) % MOD  
for i in pf.values():
  ans*=comb_mod(i+n-1,n-1)
print(ans%MOD)

Submission status: Accepted

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

def comb(n,r):
  nPr=1
  fact_r=1
  for i in range(r):
    nPr*=n-i
    fact_r*=r-i
  return nPr//fact_r

N,M=map(int,input().split())
fact={}
for i in range(2,int(math.sqrt(M))+1):
  if M==1:
    break
  while(M%i==0):
    M//=i
    if not i in fact:
      fact[i]=1
    else:
      fact[i]+=1  
if M!=1:
  fact[M]=1
  
#print(fact)
answer=1
for r in fact.values():
  answer*=comb(N+r-1,r)
  answer%=MOD
  
print(answer)

Submission status: Accepted

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

def powmod(a,p):
  if p==0:
    return 1
  elif p==1:
    return a
  else:
    pow2=powmod(a,p//2)
    if p%2==0:
      return (pow2**2)%MOD
    else:
      return (a*pow2**2)%MOD

def invmod(a):
  return powmod(a,MOD-2)

def comb_mod(n,r):
  nPr=1
  fact_r=1
  for i in range(r):
    nPr*=n-i
    nPr%=MOD
    fact_r*=r-i
    fact_r%=MOD  
  return (nPr*invmod(fact_r))%MOD

N,M=map(int,input().split())
fact={}
for i in range(2,int(math.sqrt(M))+1):
  if M==1:
    break
  while(M%i==0):
    M//=i
    if not i in fact:
      fact[i]=1
    else:
      fact[i]+=1  
if M!=1:
  fact[M]=1
  
#print(fact)
answer=1
for r in fact.values():
  answer*=comb_mod(N+r-1,r)
  answer%=MOD
  
print(answer)