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 comb_mod(n,r,mod):
    a,b=1,1
    r = min(r,n-r)
    for i in range(r):
        a = a*(n-i) % mod
        b = b*(r-i) % mod
    return a * pow(b, mod-2, mod) % mod

def prime_factor(x):
    
    prime_factor=[]
    
    for i in range(2,int(x**0.5)+1):
        if x==1: break

        count = 0
        while x%i == 0:
            x //= i
            count += 1
        if count>0:
            prime_factor.append((i,count))
    
    if x>1: prime_factor.append((x,1))
    
    return prime_factor

MOD = 10**9 + 7

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

m_fac = prime_factor(m)

ans = 1
for value,count in m_fac:
    ans = (ans * comb_mod(count+n-1,count,MOD)) %MOD
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N,M = map(int,input().split())
def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a = 1
  b = 1
  c = 1
  for i in range(1,n+1):
    a = (a*i)%p
  for i in range(1,k+1):
    b = (b*i)%p
  for i in range(1,n-k+1):
    c = (c*i)%p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  """a^b mod 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
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
num = prime_factorize(M)
numc = Counter(num)
nums = list(numc.values())
if nums:
    H = [0 for i in range(max(nums)+1)]
    for i in set(nums):
        H[i] = comb(N+i-1,i,mod)
    ans = 1
    for i in nums:
        count = H[i]
        ans = (ans*count)%mod
    print(ans)
else:
    print(1)

Submission status: Accepted

Solution code:
import sys
from collections import Counter

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

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

def prime_factorize(n): # Nの素因数分解
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

def combination(n, x, mod=10**9+7):
    # nCx 組み合わせ ex) combination(5, 2) = 10
    factorial = [1] * (n+1)
    t = 1
    for i in range(1, n+1):
        t = (t * i) % mod
        factorial[i] = t
    tmp = factorial[n]
    tmp = (tmp * pow(factorial[x], mod-2, mod)) % mod
    tmp = (tmp * pow(factorial[n-x], mod-2, mod)) % mod
    return tmp

A = prime_factorize(M)
counter = Counter(A)
answer = 1
for c in counter.values():
    answer *= combination((N-1+c), c)
    answer %= MOD

print(answer)
# 19

Submission status: Accepted

Solution code:
from collections import Counter

n, m = map(int, input().split())
MOD = 10 ** 9 + 7
SIZE = 10 ** 5 * 2
fact = [0] * SIZE
inv = [0] * SIZE
finv = [0] * SIZE
fact[0], fact[1] = 1, 1
inv[1] = 1
finv[0], finv[1] = 1, 1
for i in range(2, SIZE):
    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 modcomb(n, r):
    if n < 0 or r < 0 or n < r:
        return 0
    return fact[n] * (finv[r] * finv[n - r] % MOD) % MOD


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


counter = Counter(prime_factorize(m))
ans = 1
for v in counter.values():
    ans *= modcomb(v + n - 1, n - 1)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
from math import floor, sqrt
from collections import defaultdict
def factors(n):
    d = defaultdict(int)
    for i in range(2,floor(sqrt(n))+1):
        while n % i == 0:
            n //= i
            d[i] += 1
        if n == 1:
            break
    if n != 1:
        d[n] += 1
    return d
def inv(x, mod):
    k = mod - 2
    ret = 1
    while k > 0:
        if k&1:
            ret = (ret*x) % mod
        x = (x*x) % mod
        k >>= 1
    return ret
N, M = map(int,input().split())
mod = 10**9+7
dic = factors(M)
K = len(dic)
SIZE = N+max(dic.values()) if dic.values() else N
fact = [None]*(SIZE+1)
finv = [None]*(SIZE+1)
fact[0] = 1
for i in range(1,SIZE+1):
    fact[i] = (fact[i-1]*i) % mod
finv[SIZE] = inv(fact[SIZE], mod=mod)
for i in range(SIZE, 0, -1):
    finv[i-1] = (finv[i]*i) % mod
def comb(n,k):
    tmp = (finv[k]*finv[n-k]) % mod
    return (fact[n]*tmp) % mod
ans = 1
for p in dic:
    ans = (ans*comb(dic[p]+N-1, dic[p])) % mod
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter


MOD = 10 ** 9 + 7


def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

    invs = [1] * (n + 1)
    invs[n] = pow(modFacts[n], MOD - 2, MOD)
    for i in range(n, 1, -1):
        invs[i - 1] = (invs[i] * i) % MOD

    return modFacts, invs


def factorization(n):
    arr = Counter()
    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[i] = cnt

    if temp != 1:
        arr[temp] = 1

    if len(arr.keys()) == 0 and n != 1:
        arr[n] = 1

    return arr


N, M = map(int, input().split())
modFacts, invs = prepare(N + 100)
primes = factorization(M)

ans = 1
for p in list(primes.keys()):
    q = primes[p]
    ans *= modFacts[q + N - 1] * invs[q] * invs[N - 1]
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
import math


class Solution:

    def solve(self, N: int, M: int) -> int:

        mod = 10**9+7
        INT_MAX = 10**9

        # calculate {m+n}C{n}

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

        def modinv(a, m):
            g, x, y = egcd(a, m)
            if g != 1:
                raise Exception('modular inverse does not exist')
            else:
                return x % m

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

        # solve

        m = M
        answer = 1
        factors = {}
        for i in range(2, int(math.sqrt(M))+1):
            factor = 0
            while m % i == 0:
                m //= i
                factor += 1

            if factor > 0:
                answer *= combination(N + factor - 1, N - 1, mod=mod)
                answer %= mod

        if m > 1:
            answer *= N
            answer %= mod

        return answer


if __name__ == '__main__':

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

    # solve
    solution = Solution()
    print(solution.solve(N, M))

Submission status: Accepted

Solution code:
from math import sqrt,floor
def comb(n,m):
  if m == 0:
    return 1
  return comb(n-1,m-1)*n // m
n,m=map(int,input().split())
mod=10**9+7
def factorization(x):
  ans=[]
  for i in range(2,floor(sqrt(x))+1):
    if x%i==0:
      cnt=0
      while x%i==0:
        x//=i
        cnt+=1
      ans.append([i,cnt])
      if x==1:
        break
  if x!=1:
    ans.append([x,1])
  return ans
g=factorization(m)
ans=1
for i in g:
  ans=(ans*(comb(i[1]+n-1,i[1])%mod))%mod
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
from operator import mul
from functools import reduce
if M==1:
  print(1)
else:
  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 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

  a=factorization(M)
  A=[]
  for i in range(len(a)):
    A.append(a[i][1])
  ans=1
  for i in A:
    d=cmb(i+N-1,i)
    ans*=d%(10**9+7)
  print(ans%(10**9+7))

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
from operator import mul
from functools import reduce
if M==1:
  print(1)
else:
  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 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

  a=factorization(M)
  A=[]
  for i in range(len(a)):
    A.append(a[i][1])
  ans=1
  for i in A:
    d=cmb(i+N-1,i)
    ans*=d%(10**9+7)
  print(ans%(10**9+7))

Submission status: Accepted

Solution code:
from collections import defaultdict
n,m=map(int,input().split())
mod=10**9+7
kaidan=[1]*(2*10**5+1)
gyaku=[1]*(2*10**5+1)

for i in range(1, 2*10**5):
    kaidan[i]=i*kaidan[i-1] % mod
    gyaku[i]=pow(kaidan[i],mod-2,mod)
def comb(a,b):
    if a>0 and b>0 and a-b>0:
        return (kaidan[a] * gyaku[b]*gyaku[a-b])%mod
    elif a==0 or b==0 or a-b==0:
        return 1
    else:
        return 0
def fctr1(n): 
    f=[]
    c=0
    r=int(n**0.5)
    for i in range(2,r+2):
        while n%i==0:
            c+=1
            n=n//i
        if c!=0:
            f.append([i,c])
            c=0
    if n!=1:
        f.append([n,1])
    return f
# soin=defaultdict(int)
# while m>=2:
#     for i in range(2,int(n**.5)+5):
#         while m%i==0 and m!=0:
#             m//=i
#             soin[i]+=1
#             if m==1:
#                 break
     
L=list(fctr1(m))
ans=1
for a,l in L:
    ans*=comb(l+n-1,l)
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input()) # n=1
def inpm(): return map(int,input().split()) # x=1,y=2
def inpl(): return list(map(int, input().split())) # a=[1,2,3,4,5,...,n]
def inpls(): return list(input().split())  # a=['1','2','3',...,'n']
def inplm(n): return list(int(input()) for _ in range(n)) # x=[] 複数行
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)] # [[2,2,2,2],[1,1,1,1],[3,3,3,3]] 
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)]) # [[1,1,1,1],[2,2,2,2],[3,3,3,3]] 

def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return [w[0],w[1]]
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return ( m + x%m ) % m
    
def nCk(n,k):
    res = 1
    a=n-k
    b=k
    for i in range(1,a+b+1):
        res = res*i%mod
    for i in range(1,a+1):
        res = res*mod_inv(i,mod)%mod
    for i in range(1,b+1):                                 
        res = res*mod_inv(i,mod)%mod
    return res
def nHr(n,r):
    return nCk(n+r-1,r)

def div3(x): #素因数分解配列 dict格納型
    div=defaultdict(int)
    check=2
    while(x!=1 and check <= int(x**0.5)+2):
        while x%check==0:
            div[check]+=1
            x/=check
        check+=1
    if x != 1:
      div[x] += 1
    return div

def main():
    n,m = inpm()
    div = div3(m)
    ans = 1
    for e in div:
        ans = (ans * nHr(n,div[e])) % mod
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def primeFactors(n):
    res = []
    while n%2==0:
        res.append(2)
        n //= 2
    x = 3
    while n>1 and n>=x*x:
        while n%x==0:
            res.append(x)
            n //= x
        x += 2
    if n>1:
        res.append(n)
    return res

class BiCoeff(object):
    def __init__(self, MAX, m):
        super(BiCoeff, self).__init__()
        fac = [0]*MAX
        finv = [0]*MAX
        inv = [0]*MAX

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

        self.MAX = MAX
        self.m = m
        self.fac = fac
        self.finv = finv
        self.inv = inv

    def calc(self,n,k):
        if n<k:
            return 0
        if n<0 or k<0:
            return 0
        return (self.fac[n] * (self.finv[k]*self.finv[n-k])%self.m)%self.m

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

bicoeff = BiCoeff(n+100,MOD)

d = defaultdict(int)
for p in primeFactors(m):
    d[p] += 1

res = 1
for v in d.values():
    res *= bicoeff.calc(n-1+v,n-1)
    res %= MOD
print(res)

Submission status: Accepted

Solution code:
def ord(N,n):#N,nは正の整数、Nで割り切れる回数、許容はN^1000
    if n%N!=0:
        return 0
    else:
        return 1+ord(N,n//N)

def get_sieve_of_eratosthenes_new(n):
    import math
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    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]

primelist=get_sieve_of_eratosthenes_new(32*(10**2))

def cmb(n, r, mod):#コンビネーションの高速計算　
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 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 )


def main():
    N,M=map(int,input().split())
    product=1
    for i in range(0,len(primelist)):
        product=(product*cmb(ord(primelist[i],M)+N-1,N-1,mod))%mod
        M=M//primelist[i]**ord(primelist[i],M)
    if M!=1:
        product=(product*N)%mod
    print(product)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
from collections import defaultdict
import copy

def main():
    N,M = map(int,input().split())
    d = defaultdict(int)
    MOD = 10**9+7
    R = 10**5+100
    fac = [0 for _ in range(R+1)]
    fac[0],fac[1] = 1,1
    inv = copy.deepcopy(fac)
    invfac = copy.deepcopy(fac)
    
    for i in range(2,R+1):
        fac[i] = (fac[i-1]*i)%MOD
        inv[i] = MOD-(MOD//i)*inv[MOD%i]%MOD
        invfac[i] = (invfac[i-1]*inv[i])%MOD
        
    def coef(x,y):
        num = (((fac[x+y]*invfac[y])%MOD)*invfac[x]%MOD)
        return num

    while M%2 == 0:
        d[2] += 1
        M //= 2
    f = 3
    while f ** 2 <= M:
        if M % f == 0:
            d[f] += 1
            M //= f
        else:
            f += 2
    if M != 1:
        d[M] += 1
    
    l = list(d.values())
    ans = 1
    for num in l:
        ans *= coef(num,N-1)
        ans %= MOD
        
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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


def prime_factorization(n):  # 素因数分解
    res = []
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            cnt = 0
            while n % i == 0:
                cnt += 1
                n //= i
            res.append((i, cnt))
    if n > 1:
        res.append((n, 1))
    return res


def binomial_coefficient(n, r, mod=10**9+7):
    """
    二項係数nCr, (n,r)をmodで除したあまりを返す
    """
    res = 1
    div = 1
    r = min(r, n - r)
    for i in range(r):
        res *= (n - i) % mod
        div *= (i + 1) % mod
    res *= pow(div, mod - 2, mod)
    return res % mod


pf = prime_factorization(M)
ans = 1
for _, x in pf:
    ans = (ans * binomial_coefficient(N+x-1, x, mod)) % mod
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
import math
input = sys.stdin.readline
N, M = [int(x) for x in input().strip().split()]
d = defaultdict(int)
M_ = M
MOD = 10 ** 9 + 7

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

while True:
    for i in range(2, int(M_ ** 0.5) + 1):
        if M_ % i == 0:
            M_ //= i
            d[i] += 1
            break
    else:
        if M_ != 1:
            d[M_] += 1
        break

maxi = max(d.values())
fact = [0] * (maxi + N + 1)
p = 1

def nCr(n, r):
    if r > n - r:
        r = n - r
    if r == 0:
        return 1
    if r == 1:
        return n

    ret = 1
    for i in range(1, r+1):
        ret *= (n-(i-1))
        ret //= i

    return ret

ans = 1
nCr_d = {}
for key, val in d.items():
    if (val+N-1, N-1) not in nCr_d:
        nCr_d[(val+N-1, N-1)] = nCr(val+N-1, N-1)
    ans = (ans * nCr_d[(val+N-1, N-1)]) % MOD

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
import math
input = sys.stdin.readline
N, M = [int(x) for x in input().strip().split()]
d = defaultdict(int)
M_ = M
MOD = 10 ** 9 + 7

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

while True:
    for i in range(2, int(M_ ** 0.5) + 1):
        if M_ % i == 0:
            M_ //= i
            d[i] += 1
            break
    else:
        if M_ != 1:
            d[M_] += 1
        break

maxi = max(d.values())
fact = [0] * (maxi + N + 1)
p = 1

def nCr(n, r):
    if r > n - r:
        r = n - r
    if r == 0:
        return 1
    if r == 1:
        return n

    ret = 1
    for i in range(n, n-r, -1):
        ret *= i
    for i in range(2, r+1):
        ret //= i

    return ret

ans = 1
nCr_d = {}
for key, val in d.items():
    if (val+N-1, N-1) not in nCr_d:
        nCr_d[(val+N-1, N-1)] = nCr(val+N-1, N-1)
    ans = (ans * nCr_d[(val+N-1, N-1)]) % MOD

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
d=dict()
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**6+10
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 )
for i in range(1,int(m**0.5)+1):
  cnt=0
  while m%(i+1)==0:
    cnt+=1
    m//=(i+1)
  if cnt>0:
    if i+1 not in d:
      d[i+1]=cnt
    else:
      d[i+1]+=cnt
if m>1:
  if m not in d:
    d[m]=1
  else:
    d[m]+=1
d=list(d.items())
ans=1
for p,root in d:
  ans*=cmb(root+n-1,n-1,mod)
  ans%=mod
print(ans%mod)

Submission status: Accepted

Solution code:
from math import sqrt

N, M = [int(_) for _ in input().split()]

p = []
m = M
max_x = 1
for i in range(2, int(sqrt(m)) + 1):
    if m % i == 0:
        cnt = 0
        while m % i == 0:
            cnt += 1
            m //= i
        p.append((i, cnt))
        if cnt > max_x:
            max_x = cnt
if m > 1:
    p.append((m, 1))

kaijo = [0] * (max_x + 1 + N)
gyaku = [0] * (max_x + 1 + N)
kaijo[0] = kaijo[1] = 1
gyaku[0] = gyaku[1] = 1

MOD = 10 ** 9 + 7
for i in range(2, len(kaijo)):
    kaijo[i] = (kaijo[i - 1] * i) % MOD
for i in range(2, len(gyaku)):
    gyaku[i] = pow(kaijo[i], MOD - 2, MOD)
# print(kaijo)
# print(gyaku)
ans = 1
for x, y in p:
    a = y + (N - 1)
    b = (N - 1)
    spam = (kaijo[a] * gyaku[a - b] * gyaku[b]) % MOD
    ans = (ans * spam) % MOD
print(ans)

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
# 約数列挙
def find_divisor(n):
    divisors=[]
    for i in range(1, int(sqrt(n)) + 1):
        if n % i == 0:
            divisors.append(i)
            if i*i!=n:
                divisors.append(n // i)
    return divisors


# 素因数分解
def prime_factorization(n):
    fact=defaultdict(int)
    for i in range(2, int(sqrt(n)) + 1):
        while n % i == 0:
            n //= i
            fact[i]+=1
    if n!=1:
        fact[n]+=1
    return fact

#mint
class ModInt:
    def __init__(self, x):
        self.x = x % mod
    
    def __str__(self):
        return str(self.x)
    
    __repr__ = __str__

    def __add__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x + other.x)
        else:
            return ModInt(self.x + other)

    __radd__ = __add__
        
    def __sub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x - other.x)
        else:
            return ModInt(self.x - other)

    def __rsub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(other.x - self.x)
        else:
            return ModInt(other - self.x)

    def __mul__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * other.x)
        else:
            return ModInt(self.x * other)

    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * pow(other.x, mod-2,mod))
        else:
            return ModInt(self.x * pow(other, mod - 2, mod))
            
    def __rtruediv(self, other):
        if isinstance(other, self):
            return ModInt(other * pow(self.x, mod - 2, mod))
        else:
            return ModInt(other.x * pow(self.x, mod - 2, mod))
            

    def __pow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(self.x, other.x, mod))
        else:
            return ModInt(pow(self.x, other, mod))
            

    def __rpow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(other.x, self.x, mod))
        else:
            return ModInt(pow(other, self.x, mod))

class BigCombination(object):

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

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

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

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

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

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

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

def main():
    N,M=MI()
    ans = ModInt(1)
    B=BigCombination()
    for p,v in prime_factorization(M).items():
        ans *= B.get_combination(v+N-1,v)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(100000)
MOD = pow(10, 9) + 7
def powmod(m, p):
    if p == 0:
        return 1
    tmp = powmod(m, p // 2)
    if p & 1:
        return (tmp * tmp % MOD) * m % MOD
    else:
        return tmp * tmp % MOD


def main():
    n, m = map(int, input().split())
    div = defaultdict(lambda : 0)
    i = 2
    while i * i <= m:
        while m % i == 0:
            m //= i
            div[i] += 1
        i += 1
    if m > 1:
        div[m] += 1

    ans = 1
    for k, v in div.items():
        cn = v + n - 1
        v = min(v, cn - v)
        for i in range(v):
            ans *= cn - i
            ans %= MOD
        
        for i in range(2, v + 1):
            ans *= powmod(i, MOD - 2)
            ans %= MOD
    
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
MOD = 10**9+7
MAXN = N+200
fac = [1,1] + [0]*MAXN
finv = [1,1] + [0]*MAXN
inv = [0,1] + [0]*MAXN
for i in range(2,MAXN+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

def ncr(n,r):
    if n < r: return 0
    if n < 0 or r < 0: return 0
    return fac[n] * (finv[r] * finv[n-r] % MOD) % MOD
def nhr(n,r):
    return ncr(n+r-1, r)

from collections import Counter
def factorize(n):
    d = Counter()
    m = 2
    while m*m <= n:
        while n%m == 0:
            n //= m
            d[m] += 1
        m += 1
    if n > 1:
        d[n] += 1
    return d

factors = factorize(M)
ans = 1
for v in factors.values():
    n = nhr(N,v)
    ans *= n
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

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

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

    return arr

def cmb(n,m):
    ans=1
    for i in range(n,n-m,-1):
        ans*=i
    for i in range(1,m+1):
        ans //=i
    return ans





def resolve():
    N,M=map(int,input().split())
    ans=1
    md=10**9+7
    if M==1:
        print(1)
        return
    for i in factorization(M):
        nn=i[1]+N-1
        ans *= cmb(nn,i[1])
        ans %=  md

    print(ans)
if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
from scipy.misc import comb
# from scipy.special import comb


N, M = map(int, input().split())
MOD = 10**9+7
# M を素因数分解
rest = M
ans = 1
for i in range(2, int(M ** 0.5) + 1):
    cnt = 0
    while rest % i == 0:
        cnt += 1
        rest //= i
    # cnt が 2^X 1とか 3^X の X の部分
    ans *= comb(N+cnt-1, N-1, exact=True)
    ans %= MOD
if rest != 1:
    cnt = 1
    ans *= comb(N+cnt-1, N-1, exact=True)
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
# 逆元
# a^{-1} mod を計算する
def mod_inv(a, m):
    return pow(a, m-2, m)


def combination(a, b):
    if b > a - b:
        return combination(a, a - b)

    # 10C3 = (10*9*8)/(3*2*1)
    # 10*9*8 -> ans_mul
    # 3*2*1 -> ans_div
    ans_mul = 1
    ans_div = 1
    for i in range(b):
        ans_mul *= a - i
        ans_div *= i + 1
        ans_mul %= MOD
        ans_div %= MOD
    # ans_mul / ans_div をやりたい
    # ans_div の逆元を使って求める
    ans = ans_mul * mod_inv(ans_div, MOD)
    return ans


N, M = map(int, input().split())
MOD = 10**9+7
# M を素因数分解
rest = M
ans = 1
for i in range(2, int(M ** 0.5) + 1):
    cnt = 0
    while rest % i == 0:
        cnt += 1
        rest //= i
    # cnt が 2^X 1とか 3^X の X の部分
    ans *= combination(N+cnt-1, N-1)
    ans %= MOD
if rest != 1:
    cnt = 1
    ans *= combination(N+cnt-1, N-1)
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
from math import sqrt
from scipy.misc import comb

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


def sieve(x):
    primes = []
    li = list(range(2, x + 1))

    while li[0] <= sqrt(x):
        p = li[0]
        primes.append(p)
        li = [e for e in li if e % p != 0]

    primes += li
    return primes


def prime_fact(x):
    primes = sieve(int(sqrt(x)) + 1)
    d = {}

    for p in primes:
        cnt = 0
        while x % p == 0:
            x //= p
            cnt += 1

        if cnt:
            d[p] = cnt

    if x != 1:
        d[x] = 1

    return d


pf = prime_fact(m)
ans = 1
for v in pf.values():
    ans *= comb(v + n - 1, v, exact=True)
    ans %= mod

print(ans)