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
from functools import reduce
from operator import mul


def get_factors(n):
    """
    素因数分解
    :param int n:
    :type: list of int
    """
    if n <= 1:
        return []

    ret = []
    while n > 2 and n % 2 == 0:
        ret.append(2)
        n //= 2
    i = 3
    while i <= math.sqrt(n):
        if n % i == 0:
            ret.append(i)
            n //= i
        else:
            i += 2
    ret.append(n)
    return ret


def comb(n, r):
    """
    組み合わせの数 nCr
    :param n:
    :param r:
    :return:
    """
    r = min(n - r, r)
    if r == 0:
        return 1
    return reduce(mul, range(n, n - r, -1)) // reduce(mul, range(r, 0, -1))


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

# divs = sorted(get_divisors(m))
# # dp[d]: 累積積が d となる数列の数
# dp = {d: 1 for d in divs}
# for _ in range(n - 1):
#     for i in reversed(range(len(divs))):
#         div = divs[i]
#         dp[div] = sum([dp[d] for d in divs if div % d == 0]) % MOD
#     print(dp)
# print(dp)
# おそい


factors = get_factors(m)
counts = Counter(factors)
# k**v を全部かけあわせたやつが m に一致する
# print(functools.reduce(operator.mul, [k ** v for k, v in counts.items()]))

# v 個の k を n 個の数に配分する組み合わせの数
# → v + (n-1) 個のスペースへの v の置き方の組み合わせの数
ans = 1
for k, v in counts.items():
    ans *= comb(v + (n - 1), v)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
from math import factorial as fact
from operator import mul
from functools import reduce
import sys
input = sys.stdin.readline


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


N, M = map(int, input().split())
num = []
p_flag = [True]*(int(M**0.5)+2)

for i in range(2, int(M**0.5)+2):
    if p_flag:
        for j in range(2*i, int(M**0.5)+2, i):
            p_flag[j] = False

        cnt = 0
        while M % i == 0:
            cnt += 1
            M //= i
        if cnt > 0:
            num.append(cnt)
        if M == 1:
            break
else:
    num.append(1)

ans = 1
for i in num:
    ans = (ans * cmb(N-1+i, i)) % (10**9+7)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import math
MOD = 1000000007  # type: int


def factorization(n: int):
    if n == 1:
        return []
    factors = None
    for i in range(2, math.ceil(math.sqrt(n))+1):
        if n % i == 0:
            factors = [i] + factorization(n // i)
            break
    if factors == None:
        return [n]
    else:
        return factors


def comb(i: int, j: int):
    if j > i-j:
        return comb(i, i-j)
    mul = 1
    for k in range(i-j+1, i+1):
        mul *= k
    for k in range(2, j+1):
        mul //= k
    #print(f"{i}C{j} = {mul}")
    return mul


def solve(N: int, M: int):
    factor = factorization(M)
    factorDict = {}
    for f in factor:
        if f not in factorDict:
            factorDict[f] = 0
        factorDict[f] += 1
    mul = 1
    for k in factorDict:
        mul = (mul*comb(factorDict[k]+N-1, factorDict[k])) % MOD
    print(mul)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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:
from math import factorial, sqrt
N,M=map(int,input().split())
prms={}
tmp=M
for i in range(2, int(sqrt(M))+2):
    while not tmp%i:
        if not i in prms:
            prms[i]=1
        else:
            prms[i]+=1
        tmp //= i
if tmp != 1:
    prms[tmp] = 1

# print(prms)

res=1
def cmb(a,b):
    res=1
    if a - b < b:
        b = a-b
    for i in range(b):
        res *= (a-i)
        res //= (i+1)
    return res

for p, cnt in prms.items():
    res *= cmb(cnt+N-1, cnt)
    res %= 1000000007

print(res % 1000000007)

Submission status: Accepted

Solution code:
import math
def soinsu(N):
    sqr = int(math.sqrt(N))
    lis = []
    for i in range(2,sqr+2):
        while N % i == 0:
            lis.append(i)
            N = N // i
    if not N == 1:
        lis.append(N)
    return lis
mod = 1000000007
def modpow(a,b,MOD=mod):
    res = 1
    while b > 0:
        if (b & 1) == 1:
            res = (res*a) % MOD
        a = (a*a) % MOD
        b = b >> 1
    return res
fact = []
def ncrinit(MOD=mod):
    fact.append(1)
    for i in range(1,110005):
        fact.append((fact[i-1]*i)%MOD)

def calcnCr(n,r,MOD=mod):
    up = fact[n]
    down = modpow((fact[n-r]*fact[r])%mod,mod-2,mod)
    return (up*down)%mod

def compres(lis):
    li = []
    se = set(lis)
    for i in se:
        li.append(lis.count(i))
    return li
res = 1
N,M = list(map(int,input().split()))
ncrinit()
co = compres(soinsu(M))
for i in co:
    res = (res* (calcnCr(i+N-1,i)))%mod
print(res)

Submission status: Accepted

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

MOD = 10 ** 9 + 7

d = []

for i in range(2, int(math.sqrt(M))+2):
    if M % i == 0:
        d.append(0)
    while M % i == 0:
        d[-1] += 1
        M //= i
if M != 1:
    d.append(1)

def comb(n, k):
    a = 1
    for i in range(k):
        a *= (n-i)
    for i in range(k):
        a //= (i+1)
    return a

answer = 1
for i in d:
    answer *= comb(i+N-1, i)
    answer %= MOD

print(answer)

Submission status: Accepted

Solution code:
import math

N,M=map(int,input().split())
dic={}
for i in range(2,int(M**0.5)+1):
    if M%i==0:
        dic.setdefault(i,1)
        M//=i
        while M%i==0:
            dic[i]+=1
            M//=i
    if M==1: break

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


ans=1
for k in dic.keys():
    x=dic[k]
    tmp=1
    for i in range (N,x+N):
        tmp*=i
    ans*=tmp//math.factorial(x)
    ans%=1000000007
print(ans%1000000007)

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce

# 素因数分解して、重複組み合わせを数える。
n,m = map(int,input().split())
MOD = 10**9+7

# 素因数分解
def factorize(n):
    fct = [] # Prime Factor
    b, e = 2, 0
    while b*b <= n:
        while n % b == 0:
            n //= b
            e += 1
        if e > 0:
            fct.append((b,e))
        b, e = b+1, 0
    if n>1:
        fct.append((n,1))
    return fct

# 組み合わせ計算(nCr)
def nCr(n,r):
    r = min(r,n-r)
    if r == 0:
        return 1
    over = reduce(mul, range(n,n-r,-1))
    under = reduce(mul,range(1,r+1))
    return over // under

f = factorize(m)
ans=1
for p,num in f:
    ans *= nCr(num+n-1,num)
    ans %= MOD
    
print(ans)

Submission status: Accepted

Solution code:
def main():
    def nCr(n,r):
        a=1
        x=n
        while(x!=n-r):
          a*=x
          x-=1
        b=1
        x=r
        while(x!=0):
          b*=x
          x-=1
        return a//b

    INF=10**9+7
    N,m=map(int,input().split())


    sum=1
    yd = {}
    i = 2
    while m != 1:
      while m % i == 0:
        if i in yd:
          yd[i] += 1
        else:
          yd[i] = 1
        m //= i
      i += 1
    for b in yd.values():
        if b<N-1:
            sum*=nCr(N-1+b,b)
        else:
            sum*=nCr(N-1+b,N-1)
        sum%=INF  
    print(sum)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def nCr(n,r):
    a=1
    x=n
    while(x!=n-r):
      a*=x
      x-=1
    b=1
    x=r
    while(x!=0):
      b*=x
      x-=1
    return a//b

INF=10**9+7
N,m=map(int,input().split())


sum=1
yd = {}
i = 2
while m != 1:
  while m % i == 0:
    if i in yd:
      yd[i] += 1
    else:
      yd[i] = 1
    m //= i
  i += 1
for b in yd.values():
    if b<N-1:
        sum*=nCr(N-1+b,b)
    else:
        sum*=nCr(N-1+b,N-1)
    sum%=INF  
print(sum)

Submission status: Accepted

Solution code:
from math import factorial
from math import sqrt
def nCr(n,r):
    a=1
    x=n
    while(x!=n-r):
      a*=x
      x-=1
    b=1
    x=r
    while(x!=0):
      b*=x
      x-=1
    return a//b

INF=10**9+7
N,m=map(int,input().split())


sum=1
yd = {}
i = 2
while m != 1:
  while m % i == 0:
    if i in yd:
      yd[i] += 1
    else:
      yd[i] = 1
    m //= i
  i += 1
for b in yd.values():
    sum*=nCr(N-1+b,b)
    sum%=INF
print(sum)

Submission status: Accepted

Solution code:
from math import factorial
from math import sqrt
def nCr(n,r):
    return factorial(n)//(factorial(r)*factorial(n-r))
"""
def factorize(p):
    b=[]

    for i in range(2,int(sqrt(p)+2)):
        a=0
        while((p%i)==0):
            a+=1
            p=p//i
          
        if a!=0:
            b.append(a)
        if p==1:
          break
    return b
"""

INF=10**9+7
N,m=map(int,input().split())


sum=1
#B=factorize(M)
yd = {}
i = 2
while m != 1:
  while m % i == 0:
    if i in yd:
      yd[i] += 1
    else:
      yd[i] = 1
    m //= i
  i += 1
for b in yd.values():
    sum*=nCr(N-1+b,N-1)
    sum%=INF
print(sum)

Submission status: Accepted

Solution code:
inpl = lambda: list(map(int,input().split()))
MOD = 10**9 + 7
N, M = inpl()
 
def factorize(n):
  factorize_list = []
  i = 2
  while i*i <= n:
    k = 0
    while n % i == 0:
      n //= i
      k += 1
    if k > 0:
      factorize_list.append(k)
    i += 1
  if n > 1:
    factorize_list.append(1)
  return(factorize_list)

def H(n,k):
  h = 1
  L = n + k - 1
  k = min(n-1,k)
  for j in range(k):
    h *= L-j
  for j in range(k):
    h //= j+1
  return h

ans = 1
for k in factorize(M):
  ans *= H(N,k) % MOD
  ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
inpl = lambda: list(map(int,input().split()))
MOD = 10**9 + 7
N, M = inpl()
 
def factorize(n):
  prime_list = []
  factorize_list = []
  i = 2
  while i*i <= n:
    for p in prime_list:
      if i % p == 0:
        break
    else:
      prime_list.append(i)
      k = 0
      while n % i == 0:
        n //= i
        k += 1
      factorize_list.append(k)
    i += 1
  if n > 1:
    factorize_list.append(1)
  return(factorize_list)

def H(n,k):
  h = 1
  L = n + k - 1
  k = min(n-1,k)
  for j in range(k):
    h *= L-j
  for j in range(k):
    h //= j+1
  return h

ans = 1
for k in factorize(M):
  ans *= H(N,k) % MOD
  ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
# 素因数分解
def factorization(N):
    prime = primelist(int(N**(1/2))+2)
    factor = [0 for i in range(int(N**(1/2)+2))]
    isprime = False
    for i in prime:
        while N % i == 0:
            N = N // i
            factor[i] += 1
    if sum(factor) == 0:
        isprime = True
    if N != 1:
        factor.append(1)
    return factor, isprime

# 素数
def primelist(N):
    prime = [2]
    for i in range(3, N+1):
        flag = 1
        for j in prime:
            if i % j == 0:
                flag = 0
                break
        if flag == 1:
            prime.append(i)
    return prime

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
factor = factorization(M)[0]
ans = 1


for i in factor:
    ans *= cmb(N+i-1, i)
    ans %= 1000000007

print(ans)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
import math
import collections
def tds(n):
    prime_count = collections.Counter()
    
    for i in range(2, int(math.sqrt(n)) + 2):
        while n % i == 0:
            n /= i
            prime_count[i] += 1
    if n > 1:
        prime_count[n] += 1
    
    return prime_count
c=tds(m)
ans=1
def C(n,r):
    res=1
    for i in range(n,n-r,-1):
        res*=i
    return res//math.factorial(r)
for ci in c.values():
    ans*=C(n+ci-1,ci)
    ans%=10**9+7
print(int(ans))

Submission status: Accepted

Solution code:
from math import factorial as fac
from collections import defaultdict as ddict
n,m = map(int,input().split())
d = ddict(int)
ans = 1
mod = 10**9+7
def f2(n,r):
  ret = 1
  for i in range(n,n-r,-1):
    ret *= i
  return ret
def cc(n,r):
  t = min(r,n-r)
  return f2(n,t)//fac(t)
for i in range(2,int(m**.5)+1):
  while m % i == 0:
    d[i] += 1
    m //= i
if m > 1:
  d[m] += 1
for x in d:
  ans = ans * cc(d[x]+n-1,d[x])%mod
print(ans)

Submission status: Accepted

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

P = 10**9+7
def get_soinsu(M):
    for i in range(2,1+int(M**0.5)):
        if M%i == 0:
            return [i] + get_soinsu(M//i)
    else:
        return [M]

soinsu = {}
for n in get_soinsu(M):
    soinsu[n] = 1 + soinsu.get(n,0)

def combi(n,r):
    tmp1,tmp2 = (1,1)
    for i in range(n-r+1,n+1):
        tmp1 *= i
    for i in range(2,r+1):
        tmp2 *= i
    return (tmp1//tmp2)%P

out = 1
soinsu.pop(1,None)
for n in soinsu.values():
    out *= combi(N-1+n,n)
    out %= P
print(out)

Submission status: Accepted

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

def prime(n):#素数かどうか＿素数なら1、そうでないなら0
    for i in range(2,n):
        if n%i==0:
            return 0
    return 1

#def prime_l(n):
#    for i in range(2,n+1):
#        if prime(i)==1:
#            yield i
#def prime_l(n):#n以下の素数のリスト
#    l=[1 for i in range(2,n+1)]#2からnの、n-1個 インデは-2
#    for i in range(n-1):#0からn-2 上記−２=インデ
#        if prime(i+2):
#            for j in range(2,n//(i+2)+1):#何倍のが0になるか
#                l[(i+2)*j-2]=0
#    return l

def prime_l(n):
    l=[1 for i in range(2,n+1)]#2からn インデは-2
    #sq_n=n**(1/2)
    for i in range(n-1):
        if l[i]==1:
            for j in range(2*(i+2),n+1,i+2):
                l[j-2]=0
    l1=[]
    for i in range(n-1):
        if l[i]==1:
            l1.append(i+2)
    return l1


def modpow(a,n,p):#a^n mod p
    res=1
    while n>0:
        if n&1:#１とのビット論理積が１、つまり奇数
            res=res*a%p
        a=a*a%p
        n>>=1
        #ビットの右シフト_2進数表記のnを小数点を固定して右に１桁ずらす_１桁小さくなる
    return res

if m==1:
    print(1)
else:
    #l=[i+2 for i in prime_l(int(1e9))]
    #l=prime_l(int(m**(1/2))) if m>=4 else prime_l(m)
    l=prime_l(int(m**(1/2)))#√までにしておくと、1にならずに残ったものは素数
    #ll=next(l)
    i=0
    d={}
    while m!=1 and i!=len(l):
        if m%(l[i])==0:
            d[l[i]]=1
            m/=l[i]
            while m%(l[i])==0:
                d[l[i]]+=1
                m/=l[i]
        #ll=next(l)
        i+=1
        #while l[i]==0:
        #    i+=1
    if m!=1:
        d[m]=1
    #s_k=0
    #for i in d.values():
    #    s_k+=i
    #print(d.values())
    mod=int(1e9+7)
    n_fac=1
    fac_l=[1]#0!
    d_max=max(d.values())
    #for i in range(n+d_max-1):# 1!,2!,,,,(n+d_max-1)!
    #    n_fac*=i+1
    for i in range(n+d_max-1):# 0!,1!,2!,,,,(n+d_max-1)!
        n_fac*=i+1
        n_fac=n_fac%mod
        fac_l.append(n_fac)

    fac_1_l=[]
    for i in range(n+d_max):
        fac_1_l.append(modpow(fac_l[i],mod-2,mod))
    w=1
    for dv in d.values():
        w*=fac_l[n+dv-1]
        w=w%mod
        #n_n_fac=fac_l[n-dv]
        #div=int((fac_l[n-1-1]*fac_l[dv-1])%(1e9+7))
        #print(div)
        #if div>w:
        #    w+=1e9+7
        #w=int(w/div)
        w=w*fac_1_l[n-1]%mod
        w=w*fac_1_l[dv]%mod
    print(w)

Submission status: Accepted

Solution code:
from collections import Counter
from scipy.misc import comb
c=Counter()
n,m=map(int,input().split())
t=2
#Fanction of Factoring
while(t**2 <= m):
    if m%t:
        t+=1
        continue
    while m%t==0:
        c[t]+=1
        m//=t
if m>1:c[m]+=1
a=1

for i in c:
    a=a*comb(n+c[i]-1,n-1,exact=1)%(10**9+7)
print(a)

Submission status: Accepted

Solution code:
MOD = 10**9+7
# 逆元を前計算しておくことでクエリをO(1)で返す
MAX = 10**6
fac = [0]*MAX  # fac[n]:  (n!) mod p
finv = [0]*MAX # finv[n]: (n!)^-1 mod p
inv = [0]*MAX  # inv[n]:  (n)^-1 mod p

def comb_init():
    global fac, finv, inv
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i-1] * i % MOD
        inv[i] = MOD - inv[MOD%i] * (MOD//i)%MOD
        finv[i] = finv[i-1] * inv[i] % MOD

def comb(n:int, r:int)->int:
    global fac, finv
    if n < r: return 0
    if n < 0 or r < 0: return 0
    return fac[n] * (finv[r] * finv[n-r] % MOD) % MOD

if __name__ == '__main__':
    N,M = map(int, input().split())
    ans = 1
    comb_init()
    
    #  素因数分解
    i=2
    nokori = M
    while i*i <= nokori:
        if nokori%i==0:
            cnt = 0
            while nokori%i==0:
                cnt += 1
                nokori //= i
            ans *= comb(N+cnt-1, N-1)
            ans %= MOD
        i += 1
            
    if nokori != 1:
        ans *= comb(N+1-1, N-1)
        ans %= MOD
        
    print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9+7
    
def comb(a:int, b:int):
    if b > a-b: return comb(a, a-b)
    mul = 1
    div = 1
    for i in range(b):
        mul *= a-i
        div *= i+1
        mul %= MOD
        div %= MOD
        
    ret = mul * pow(div, MOD-2, MOD)
    return ret

if __name__ == '__main__':
    N,M = map(int, input().split())
    ans = 1
    
    #  素因数分解
    i=2
    nokori = M
    while i*i <= nokori:
        if nokori%i==0:
            cnt = 0
            while nokori%i==0:
                cnt += 1
                nokori //= i
            ans *= comb(N+cnt-1, N-1)
            ans %= MOD
        i += 1
            
    if nokori != 1:
        ans *= comb(N+1-1, N-1)
        ans %= MOD
        
    print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9+7

def modpow(a:int, p:int)->int:
    # return a**p (mod MOD)
    if p==0: return 1
    if p%2==0:
        half_p = p//2
        half = modpow(a, half_p)
        return half*half % MOD
    else:
        return a * modpow(a, p-1) % MOD
    
def comb(a:int, b:int):
    if b > a-b: return comb(a, a-b)
    mul = 1
    div = 1
    for i in range(b):
        mul *= a-i
        div *= i+1
        mul %= MOD
        div %= MOD
        
    ret = mul * modpow(div, MOD-2) % MOD
    return ret

if __name__ == '__main__':
    N,M = map(int, input().split())
    ans = 1
    
    #  素因数分解
    i=2
    nokori = M
    while i*i <= nokori:
        if nokori%i==0:
            cnt = 0
            while nokori%i==0:
                cnt += 1
                nokori //= i
            ans *= comb(N+cnt-1, N-1)
            ans %= MOD
        i += 1
            
    if nokori != 1:
        ans *= comb(N+1-1, N-1)
        ans %= MOD
        
    print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from collections import Counter
from itertools import product
from math import factorial

# prime numbers
primes = list(range(int(10**5) + 1))
primes[1] = 0
for i in range(2, int(len(primes) ** 0.5) + 1):
    if primes[i]:
        for j in range(2 * i, len(primes), i):
            primes[j] = 0

def main():
    N, M = LI()
    # 素因数分解
    factors = Counter()
    for i in range(int(M ** 0.5) + 1):
        if primes[i]:
            while M % i == 0:
                factors[i] += 1
                M //= i
        if M < i:
            break
    if M != 1:
        factors[M] += 1
    ans = 1
    for k in factors.values():
        a, b = 1, 1
        for i in range(1, k + 1):
            a *= N + k - i
            b *= i
        ans = (ans * (a // b)) % MOD

    return ans % MOD

print(main())

Submission status: Accepted

Solution code:
import collections
import math
n, m = [int(item) for item in input().split()]

def trial_division_sqrt(n):
    prime_count = collections.Counter()
    for i in range(2, int(math.sqrt(n)) + 2):
        while n % i == 0:
            n /= i
            prime_count[i] += 1
    if n > 1:
        prime_count[int(n)] += 1
    return prime_count

cnt = trial_division_sqrt(m)

ans = 1
for item in cnt:
  h = 1
  k_fact = 1
  for i in range(cnt[item]):
    h *= n + cnt[item] - 1 - i
    k_fact *= (i+1)
  ans *= h
  ans = ans // k_fact
  ans = ans % (1000000000 + 7)
print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007
sys.setrecursionlimit(1000000)

#A
def A():
    return

#B
def B():
    return

#C
def C():
    s = S()
    t = S()
    n = len(s)
    d = defaultdict(list)
    for i in range(n):
        d[s[i]].append(t[i])
    d2 = defaultdict(list)
    for i in range(n):
        d2[t[i]].append(s[i])
    for i in d.keys():
        k = d[i]
        k = list(set(d[i]))
        if len(k) > 1:
            print("No")
            quit()
    for i in d2.keys():
        k = d2[i]
        k = list(set(d2[i]))
        if len(k) > 1:
            print("No")
            quit()
    print("Yes")
#D
def D():
    n,m = LI()
    if m == 1:
        print(1)
        quit()
    d = defaultdict(int)
    i = 2
    a = m
    while i**2 <= m:
        if not a%i:
            while not a%i:
                a//=i
                d[i] += 1
        i += 1
    if a != 1:
        d[a] += 1
    fact = [1 for i in range(n+31)]
    for i in range(n+30):
        fact[i+1] = fact[i]*(i+1)%mod
    inv_fact = [None for i in range(n+31)]
    inv_fact[n+30] = pow(fact[n+30],mod-2,mod)
    for i in range(n+30)[::-1]:
        inv_fact[i] = inv_fact[i+1]*(i+1)%mod
    ans = 1
    for i in d.values():
        ans *= fact[i+n-1]*inv_fact[i]*inv_fact[n-1]%mod
        ans %= mod
    print(ans)
#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Accepted

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

MOD = 1000000007  # type: int


def trial_division_sqrt(n):
    prime_count = collections.Counter()
    for i in range(2, int(math.sqrt(n)) + 2):
        while n % i == 0:
            n /= i
            prime_count[i] += 1
    if n > 1:
        prime_count[int(n)] += 1

    return prime_count


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

    numer = [n - r + k + 1 for k in range(r)]
    denom = [k + 1 for k in range(r)]

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

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

    return result


def solve(N: int, M: int):
    pc = trial_division_sqrt(M)
    ans = 1
    for c in pc:
        ans = (ans * cmb(pc[c]+N-1, pc[c])) % MOD
    print(int(ans))
    return


# Generated by 1.1.3 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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:
from collections import defaultdict
c=defaultdict(int)
n,m=map(int,input().split())
for i in range(2,int(m**0.5)+1):
    if m%i==0:
        d=0
        while m%i==0:
            d+=1
            m//=i
        else:
            c[i]+=d
            if m==1:
                break
if m!=1:
    c[m]+=1
def comb(x, y):
    y = min(y, x - y)
    a = 1
    for i in range(x, x - y, -1):
        a *= i
    b = 1
    for i in range(1, y + 1):
        b *= i
    return a // b
a=1
for i in c.values():
    a=comb(n+i-1,i)*a%(10**9+7)
print(a)

Submission status: Accepted

Solution code:
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

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 power_func(a,b,p):
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p

class comb_calclator():
    def __init__(self, N, p):
        self.N = N
        self.p = p
        self.frac_N = [0 for i in range(N + 1)]
        self.frac_N[0] = 1L
        self.comb_N = {}
        for i in range(1, N + 1):
            self.frac_N[i] = (self.frac_N[i - 1] * i ) % p

    def comb(self, n, r):
        if n<0 or r<0 or n<r: return 0
        if n==0 or r==0: return 1
        if (n, r) in self.comb_N:
            return self.comb_N[(n, r)]
        a = self.frac_N[n]
        b = self.frac_N[r]
        c = self.frac_N[n - r]
        self.comb_N[(n, r)] = (a*power_func(b,self.p-2,self.p)*power_func(c,self.p-2, self.p))% self.p
        self.comb_N[(n, n - r)] = self.comb_N[(n, r)]
        return self.comb_N[(n, r)]


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] = [int(input_raw[0]), long(input_raw[1])]
    prime = prime_decomposition(M)
    prime_num = {}
    for p in prime:
        if p not in prime_num:
            prime_num[p] = 1
        else:
            prime_num[p] += 1

    cmb = comb_calclator(N * 10, 1000000007)
    count = 1L
    for p in prime_num:
        count = (count * cmb.comb(N + prime_num[p]- 1, prime_num[p])) % 1000000007

    print count
if __name__ == '__main__':
    main()

Submission status: Accepted

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


def factorize(n):
    b = 2
    fct = {}
    while b * b <= n:
        while n % b == 0:
            n //= b
            if b in fct.keys():
                fct[b] += 1
            else:
                fct[b] = 1
        b = b + 1
    if n > 1:
        fct[n] = 1
    return fct


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


fac_list = factorize(M)
ans = 1
for k, v in fac_list.items():
    ans *= cmb(v+N-1, v)
    if ans >= mod:
        ans %= mod

print(int(ans))

Submission status: Accepted

Solution code:
import math
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
N,M = map(int,input().split())
L = prime_factor(M)
L.append(0)
K = []
cur = L[0]
cnt = 0
for i in range(len(L)):
  if cur == L[i]:
    cnt += 1
  else:
    K.append(cnt)
    cnt = 1
    cur = L[i]
ans = 1
for i in range(len(K)):
  n = K[i]+N-1
  k = N-1
  cur = 1
  for i in range(k+1,n+1):
    cur *= i
  for j in range(1,n-k+1):
    cur = cur//j
  ans *= cur%(10**9+7)
print(ans%(10**9+7))

Submission status: Accepted

Solution code:
a,b=map(int,input().split())


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

def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b += 1
    if n > 1:
        fct.append(n)
    return fct
if len(factorize(b))==0:
    print(1)
    exit()

mod=10**9+7
print(reduce(mul,map(lambda x:cmb(a-1+x,a-1),Counter(factorize(b)).values()))%mod)

Submission status: Accepted

Solution code:


def modpow(a,p):
    mod = 1000000007
    if p==0:
        return 1
    elif p%2==0:
        halfP = p/2
        half = modpow(a,halfP)
        return half * half %mod
    else:
        return a * modpow(a,p-1) % mod
    
def calccomb(a,b):
    mod = 1000000007
    if b>a-b:
        return calccomb(a,a-b)
    ansMul = 1
    ansDiv = 1
    for i in range(b):
        ansMul *= a-i
        ansDiv *= i+1
        ansMul %= mod
        ansDiv %= mod
    #ansDivの逆元
    ans = ansMul * modpow(ansDiv, mod-2)
    return ans
  
import math
N ,M =map(int,input().split())
Mnokori = M
ans = 1
for i in range(2,int(math.sqrt(Mnokori))+1):
    if Mnokori % i == 0:
        cnt = 0
        while Mnokori % i == 0:
            cnt = cnt + 1
            Mnokori /= i
        ans *= calccomb(N+cnt-1,N-1)
        ans %= 1000000007
if Mnokori != 1:
    ans *= calccomb(N+1-1,N-1)
    ans %=  1000000007
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
def div(x,y):
    if x%y!=0:
        return 0
    else:
        return 1+div(int(x/y),y)

p=[]
q=[]

def fact(s):
    if len(p)!=0:
        k=p[-1]
    else:
        k=2
    for i in range(2,max(int(s**0.5) +2,2)):
        a=div(s,i)
        if a==0:
            0
        else:
            p.append(a)
            q.append(i)
            s=int(s/i**a)
    if s!=1:
        p.append(1)
            
fact(m)
def comb(nn,rr):
    rr=min(rr,nn-rr)
    rt=1
    for i in range(rr):
        #rt=rt*(nn-i)/(rr-i)
        rt*=(nn-i)
    for i in range(rr):
        rt//=(rr-i)
    return int(rt)
#print(p,q,m)
mo=10**9 +7
ans=1
if len(p)==0:
    ans=1
else:
    for i in p:
        ans*=comb(i+n-1, i) % mo
print(ans % mo)