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

def factor(n):
    i = 2
    r = []
    while i * i <= n:
        if n % i == 0:
            c = 0
            while n % i == 0:
                c += 1
                n //= i
            r.append((i, c))
        i += 1
    if n > 1:
        r.append((n, 1))
    return r

class nCrMod():
    def __init__(self, mod):
        self.mod = mod
        self.fac = [1, 1]
        self.finv = [1, 1]
        self.inv = [0, 1]

    def prep(self, n):
        mod = self.mod
        f, fi = self.fac[-1], self.finv[-1]
        for i in range(len(self.fac), n + 1):
            fn = f * i % mod
            v = -self.inv[mod % i] * (mod // i) % mod
            fin = fi * v % mod
            f, fi = fn, fin
            self.fac.append(f)
            self.finv.append(fi)
            self.inv.append(v)

    def __call__(self, n, r):
        if len(self.fac) <= n:
            self.prep(n)
        return self.fac[n] * self.finv[r] * self.finv[n - r] % self.mod

def main():
    N, M = map(int, input().split())
    mod = 10**9 + 7
    nCr = nCrMod(mod)
    f = factor(M)
    r = 1
    for p, q in f:
        r = r * nCr(N + q - 1, q) % mod
    return r

print(main())

Submission status: Accepted

Solution code:
def prime_factorize(n):
    ans = []
    for i in range(2, int(n ** (1 / 2)) + 1):
        while True:
            if not n % i == 0:
                break
            ans.append(i)
            n /= i
        if n == 1:
            break
    if n != 1:
        ans.append(int(n))
    return ans

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

n, m = map(int, input().split())
mod = 10 ** 9 + 7
s = prime_factorize(m)
if m == 1:
    s = [1]
c = 0
d = s[0]
ans = 1
for i in range(len(s)):
    if d == s[i]:
        c += 1
    else:
        d = s[i]
        ans *= comb(n - 1 + c, c, mod)
        ans %= mod
        c = 1
ans *= comb(n - 1 + c, c, mod)
ans %= mod
if m == 1:
    ans = 1
print(ans)

Submission status: Accepted

Solution code:
class cmbs(object):
    def __init__(self, mod):
        self.mod = mod
        self.g1 = [1, 1]
        self.g2 = [1, 1]
        inverse = [0, 1]
        for i in range(2, 10 ** 6 + 1):
            self.g1.append((self.g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod // i)) % mod)
            self.g2.append((self.g2[-1] * inverse[-1]) % mod)

    def cmb(self, n, r):
        if n > 10 ** 6:
            return self.cmbl(n, r)
        return self.cmbr(n, r)

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

    def cmbl(self, n, r):
        t = 1
        r = min(r, n-r)
        for i in range(n - r + 1, n + 1):
            t = t * i % self.mod
        return t * self.g2[r] % self.mod
def prime_factorize(n):
    a = {}
    while n % 2 == 0:
        if 2 in a:
            a[2] += 1
        else:
            a[2] = 1
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            if f in a:
                a[f] += 1
            else:
                a[f] = 1
            n //= f
        else:
            f += 2
    if n != 1:
        if n in a:
            a[n] += 1
        else:
            a[n] = 1
    return a
def main():
    N, M = map(int, input().split())
    d = prime_factorize(M)
    MOD = 10**9 + 7
    c = cmbs(MOD)
    r = 1
    for i in d:
        r *= c.cmb(N+d[i]-1, N-1)
    r %= MOD
    print(r)
main()

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(n-1+v, n-1, p)
    ans %= p
print(ans)

Submission status: Accepted

Solution code:
# AC: msec(Python3)
from math import factorial
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

MOD = 10**9+7

def cmb(n, r):
    if n < 0 or r < 0:
        return 0
    if r > n:
        return 0

    r = min(n-r, r)
    res = 1
    for i in range(r):
        res *= n - i

    return res // factorial(r)


def prime_factorization(n):
    d = []
    i, e = 2, 0  # factor, exponent
    while i * i <= n:
        while n % i == 0:
            n //= i
            e += 1
        if e > 0:
            d.append((i, e))
        i += 1
        e = 0
    if n > 1:
        d.append((n, 1))
    return d


def main():
    N,M = map(int, readline().split())

    d = prime_factorization(M)

    ans = 1
    for i, e in d:
        ans *= cmb(N-1+e, e)
        ans %= MOD

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

MOD = 10**9+7

fac = [1, 1]     # 元テーブル
f_inv = [1, 1]   # 逆元テーブル
inv = [0, 1]     # 逆元テーブル計算用テーブル
def prepare(n, mod):
    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)


def cmb(n, r, mod):
    if n < 0 or r < 0:
        return 0
    if r > n:
        return 0

    return fac[n] * pow(fac[r],MOD-2,MOD) * pow(fac[n-r],MOD-2,MOD) % mod


def prime_factorization(n):
    d = []
    i, e = 2, 0  # factor, exponent
    while i * i <= n:
        while n % i == 0:
            n //= i
            e += 1
        if e > 0:
            d.append((i, e))
        i += 1
        e = 0
    if n > 1:
        d.append((n, 1))
    return d


def main():
    N,M = map(int, readline().split())

    prepare(N+100, MOD)
    d = prime_factorization(M)

    ans = 1
    for i, e in d:
        ans *= cmb(N-1+e, e, MOD)
        ans %= MOD

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

MOD = 10**9+7

fac = [1, 1]     # 元テーブル
f_inv = [1, 1]   # 逆元テーブル
inv = [0, 1]     # 逆元テーブル計算用テーブル
def prepare(n, mod):
    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inv.append((-inv[mod % i] * (mod//i)) % mod)
        f_inv.append((f_inv[-1] * inv[-1]) % mod)


def cmb(n, r, mod):
    if n < 0 or r < 0:
        return 0
    if r > n:
        return 0

    return fac[n] * f_inv[r] * f_inv[n-r] % mod


def prime_factorization(n):
    d = []
    i, e = 2, 0  # factor, exponent
    while i * i <= n:
        while n % i == 0:
            n //= i
            e += 1
        if e > 0:
            d.append((i, e))
        i += 1
        e = 0
    if n > 1:
        d.append((n, 1))
    return d


def main():
    N,M = map(int, readline().split())

    prepare(N+100, MOD)
    d = prime_factorization(M)

    ans = 1
    for i, e in d:
        ans *= cmb(N-1+e, e, MOD)
        ans %= MOD

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

MOD = 10**9 + 7

fac = [1, 1]     # 元テーブル
f_inv = [1, 1]   # 逆元テーブル
inv = [0, 1]     # 逆元テーブル計算用テーブル
def prepare(n, mod):
    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inv.append((-inv[mod % i] * (mod//i)) % mod)
        f_inv.append((f_inv[-1] * inv[-1]) % mod)


def cmb(n, r, mod):
    if n < 0 or r < 0:
        return 0
    if r > n:
        return 0

    return fac[n] * f_inv[r] * f_inv[n-r] % mod


def prime_factorization(n):
    d = {}
    i = 2
    while i * i <= n:
        if n % i == 0:
            d[i] = 1
            n //= i
            while n % i == 0:
                n //= i
                d[i] += 1
        i += 1
    if n > 1:
        d[n] = 1
    return d


def main():
    N,M = map(int, readline().split())

    prepare(N+100, MOD)
    d = prime_factorization(M)

    ans = 1
    for v in d.values():
        ans *= cmb(N-1+v, v, MOD)
        ans %= MOD

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def prime_factor(n):
    ret, p = {}, 2
    while p*p <= n:
        while n % p == 0:
            ret[p] = ret.get(p, 0) + 1
            n //= p
        p += 1
    if n != 1: ret[n] = 1
    return ret


def mod_inverse(x, mod):
    return pow(x, mod-2, mod)


def mod_comb(n, k, mod):
    numer, denom = 1, 1
    for i in range(k):
        numer = numer * ((n-i) % mod) % mod
        denom = denom * ((i+1) % mod) % mod

    return numer * mod_inverse(denom, mod) % mod


def main():
    n, m = map(int, input().split())
    prime = prime_factor(m)
    mod = 1000000007
    ans = 1
    for (p, e) in prime.items():
        ans = ans * mod_comb(n+e-1, e, mod) % mod

    print(ans)

main()

Submission status: Accepted

Solution code:
from collections import Counter
import math
div = 10**9 + 7

def pf(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())
a = Counter(pf(m))

ans = 1
for i in a:
    temp = math.factorial(a[i] + n - 1 ) // ( math.factorial(a[i]) * math.factorial(n-1) )
    ans = ans * temp % div
    
print(ans)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""


mod = 10**9+7 #出力の制限
N = 10**5+10**4
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
def p(n,r):
    if ( r<0 or r>n ):
        return 0
    return g1[n] * g2[n-r] % mod

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 )
# a = cmb(n,r)

N,M = m()

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(int(n))
  return table

def make_divisors(n): #約数列挙
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

po = prime_decomposition(M)

po = s(po)


co = 1


for i in range(len(po)):
    co *= cmb(po[i][1]+N-1,N-1)
    co %= mod
print(co)

Submission status: Accepted

Solution code:
import math

# 素因数分解
def prime_factorization(n):
    # s * s <= n
    s = math.floor(math.sqrt(n)) # 平方根を小数点切り捨て
    ans = [] # [素数, 指数]のリスト

    # 2からsまでの素因数を求める
    for i in [2] + list(range(3, s + 1, 2)):
        if n < i:
            break
        if n % i == 0:
            r = 0 # 指数カウンタクリア
            while n % i == 0:
                r += 1
                n //= i
            ans.append([i, r])

    # 残った素数を追加
    if n > s:
        ans.append([n, 1])

    return(ans)

def binomial_p(n, k, p):
    '''
    Input: integers n, k such that n >= k >= 0, prime number p
    Output: n choose k mod p
    '''
    k = min(k, n-k)

    if k == 0:
        retval = 1
    elif k == 1:
        retval = n
    else:
        numer = n  # n * (n - 1) * ... * (n - k + 1)
        inv = [0, 1]    # inv[i] : inverse of i mod p
        inv_denom = 1 # factorial of inverse of k mod p = 1^(-1) * 2^(-1) * ... * k^(-1) mod p
        for i in range(2, k + 1):
            numer = numer * (n - i + 1) % p
            inv.append(( inv[p % i] * (p - p//i) ) % p ) # inverse of i
            inv_denom = inv_denom * inv[-1] % p
        retval = numer * inv_denom % p

    return retval

###########################

N, M = [int(x) for x in input().split()]
q = 10 ** 9 + 7

if M == 1:
    ans = 1
else:
    pfact = prime_factorization(M)
    ans = 1
    for pr in pfact:
        ans = ans * binomial_p(N - 1 + pr[1], pr[1], q) % q

print(ans)

Submission status: Accepted

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

import math
def prime_division(x):
    q = int(math.sqrt(x))
    a = []
    for i in range(2,q+1):
        ex = 0
        while x%i == 0:
            ex += 1
            x //= i
        if ex>0:
            a.append([i,ex])
    if x>q:
        a.append([x,1])
    return a

def modinv2(x,r):
  return pow(x,r-2,r)

def comb(n,a,R):
    dend = 1
    for i in range(a):
        dend = (dend*(n-i))%R
    sor = 1
    for i in range(2,a+1):
        sor = (sor*i)%R
    return (dend*modinv2(sor,R))%R

n,m = inm()
pl = prime_division(m)
prod = 1
for p,e in pl:
    prod = (prod * comb(e+n-1,e,R))%R
print(prod)

Submission status: Accepted

Solution code:
#import decimal
#decimal.getcontext().prec==500 Floatの桁数を500まで増やす
#Decimal(c).sqrt() それで平方根を求める
#Decimal(1) / Decimal(7) 1/7
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd
import sys
#input = sys.stdin.readline


#N=int(input())
N,M=map(int,input().split())
mod=10**9 + 7
maxi=round(M**.5)+2
fac=[1,1]
for i in range(2,N+100):
    fac.append(fac[i-1]*i%mod)
ifac=[pow(i,mod-2,mod) for i in fac]
sosuu={}
i=2
maxi=round(M**.5)+1
while M>1 and maxi>=i:
    if M%i==0:
        sosuu[i]=0
        while M%i==0:
            M//=i
            sosuu[i]+=1
    i+=1
if M>1:
    sosuu[M]=1
count=1

for s in sosuu:
    a=sosuu[s]
    count=(count*fac[a+N-1]*ifac[N-1]*ifac[a])%mod
print(count)

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

g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
MOD = 10**9+7
for i in range(2, 2*10**5):
    g1.append((g1[-1] * i) % MOD)
    inverse.append((-inverse[MOD % i] * (MOD // i)) % MOD)
    g2.append((g2[-1] * inverse[-1]) % MOD)

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


N, M = map(int, input().split())
if M == 1:
  print(1)
  quit()

n = N - 1
fac_m = factorization(M)
ans = 1
for _, m in fac_m:
  ans *= memo_comb(m+n, n)
  ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
mod=10**9+7
n,m=map(int,input().split())
n_max=2*(10**5+1)
F,FI=[0]*(n_max+1),[0]*(n_max+1)
F[0],FI[0]=1,1
for i in range(n_max):
  F[i+1]=(F[i]*(i+1))%mod
FI[n_max-1]=pow(F[n_max-1],mod-2,mod)
for i in reversed(range(n_max-1)):
  FI[i]=(FI[i+1]*(i+1))%mod
def comb(x,y):
  return (F[x]*FI[x-y]*FI[y])%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

ans=1
for k in pf.keys():
  ans=(ans*comb(n-1+pf[k],pf[k]))%mod
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 main():
    N,M = map(int,input().split())
    b = {}
    for i in range(2,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:
N,M=map(int,input().split())
P=10**9+7
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

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

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

    return arr
a=factorization(M)
ans=1
for x in a:
    c=1
    for i in range(x[1]):
        c*=(N+x[1]-i-1)
    for i in range(x[1]):
        c//=(i+1)
    ans*=c
    ans=ans%P
if M==1:
    ans=1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
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

N,M=map(int,list(input().split(" ")))
mod=10**9+7
def factor(n):
    fct = []  
    b, e = 2, 0 
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct

fac=np.array(factor(M))
ans=1
for i in range(len(fac)):
    ans*=cmb(N+fac[i][1]-1,N-1)
print(ans%mod)

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 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

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

l = factorization(m)

ans = 1

if m == 1:
	print(ans)
else:
	for _,c in l:
		ans = ans * cmb(c+n-1,c) % MOD

	print(ans)

Submission status: Accepted

Solution code:
def factors(n):
    f = []
    c = 0
    while n % 2 == 0:
        n //= 2
        c += 1
    if c > 0:
        f.append([2, c])
    p = 3
    while p * p <= n:
        if n % p == 0:
            c = 0
            while n % p == 0:
                n //= p
                c += 1
            if c > 0:
                f.append([p, c])
        p += 2
    if n != 1:
        f.append([n, 1])
    return f

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

fact = [0] * (N+35)
finv = [0] * len(fact)
inv  = [0] * len(fact)

fact[0] = fact[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2, len(fact)):
    fact[i] = fact[i-1] * i % MOD
    inv[i] = - inv[MOD % i] * (MOD // i) % MOD
    finv[i] = finv[i - 1] * inv[i] % MOD

nCr = lambda n, r: fact[n] * finv[n-r] * finv[r] % MOD

ans = 1

for _, x in factors(M):
    ans = ans * nCr(x+N-1, x) % MOD

print(ans)

Submission status: Accepted

Solution code:
import math
from collections import Counter

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

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

ans = 1
for p, q in prime_count.items():
    ans *= ncr(q+n-1, n-1, mod)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
from collections import Counter
n,m = map(int,readline().split())
mod = 10**9+7

"""素因数分解"""
def factrize(n):
    b = 2
    fct = []
    while b*b <= n:
        while n % b == 0:
            n //= b
            #もし素因数を重複させたくないならここを加えてfct.append(b)を消す
            """
            if not b in fct:
                fct.append(b)
            """
            fct.append(b)
        b = b+1
    if n > 1:
        fct.append(n)
    return fct #リストが帰る
def pow(n,p,mod=10**9+7): #繰り返し二乗法(nのp乗)
    res = 1
    while p > 0:
        if p % 2 == 0:
            n = n ** 2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod
def factrial_memo(n=20**5+1,mod=10**9+7):
    fact = [1, 1]
    for i in range(2, n + 1):
        fact.append((fact[-1] * i) % mod)
    return fact
fact = factrial_memo()
def fermat_cmb(n, r, mod=10**9+7): #needs pow,factrial_memo(only fact). return nCk
    return fact[n] * pow(fact[r],mod-2) * pow(fact[n-r],mod-2) %mod

lst1 = factrize(m)

c = Counter(lst1)

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

print(ans)

Submission status: Accepted

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

fct = {}

for i in range(2,int(m**(1/2))+10):
    if m%i==0:##合成数で割れることはない
        fct[i]=1
        m//=i
        while m%i==0:
            fct[i]+=1
            m//=i
if m>1:
    fct[m]=1
mod = 10**9+7
def h(a,b):
    res = 1
    for i in range(a+b-1,a-1,-1):
        res *= i
        res %= mod
    for i in range(1,b+1):
        res *= pow(i,mod-2,mod)
        res %= mod
    return res
ans = 1
for p in fct:
    ans *= h(n,fct[p])
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
class Factorial():
    def __init__(self,n,mod):
        self.mod = mod
        self.factorial = [0 for _ in range(n+1)]
        self.inv = [0 for _ in range(n+1)]
        self.factorial[0] = 1
        self.inv[0] = 1
        for i in range(n):
            self.factorial[i+1] = self.factorial[i]*(i+1)%mod
        self.inv[n] = pow(self.factorial[n],mod-2,mod)
        for i in range(n)[::-1]:
            self.inv[i] = self.inv[i+1]*(i+1)%mod

    def comb(self,m,k):
        return self.factorial[m]*self.inv[k]*self.inv[m-k]%self.mod

def factorization(n):
    if n == 1: return [1]
    res = []
    x = n
    y = 2
    while y*y <= x:
        while x % y == 0:
            res.append(y)
            x //= y
        y += 1
    if x > 1: res.append(x)
    return res

from collections import Counter

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

ans = 1

if M > 1:

    F = factorization(M)
    C = Counter(F)

    fact = Factorial(200000,MOD)

    for v in C.values():
        ans *= fact.comb(N+v-1,v)
        ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
U = 10**5
T = np.zeros(U,np.int32)
T[2] = 1
T[3::2] = 1
for i in range(U):
  if i*i>U:
    break
  if T[i]:
    T[i*i::2*i] = 0
pls = np.where(T)[0]
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
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())
dic = {}
for p in pls:
  cnt = 0
  while M%p==0:
    M //= p
    cnt += 1
  dic[p] = cnt
if M!=1:
  dic[M] = 1
ans = 1
for k in dic.keys():
  ans *= cmb(dic[k]+N-1,N-1,mod)
  ans %= mod
print(ans)

Submission status: Accepted

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

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

def combination(n, r):
    ans = n
    for i in range(1, r):
        ans = ans * ((n - i) % mod) * pow(i + 1, mod - 2, mod)
        ans = ans % mod    
    return ans

c = collections.Counter(prime_factorize(M))

ans = 1
for num in c.values():
    ans = ans * combination(N - 1 + num, num)
    ans = ans % mod
print(ans)

Submission status: Accepted

Solution code:
from math import sqrt,ceil
N,M=map(int,input().split())
l=[]
for i in range(2,ceil(sqrt(M))):
    t=0
    while not M%i:
        M//=i
        t+=1
    if t:
        l.append(t)
if M>1:
    l.append(1)
MAX_NUM = 10**5 + 100
pr = 10**9+7
fac  = [0 for _ in range(MAX_NUM)]
finv = [0 for _ in range(MAX_NUM)]
inv  = [0 for _ in range(MAX_NUM)]
fac[0]  = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2,MAX_NUM):
    fac[i] = fac[i-1] * i % pr
    inv[i] = pr - inv[pr%i] * (pr // i) % pr
    finv[i] = finv[i-1] * inv[i] % pr
def c(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % pr) % pr
a=1
for i in l:
    a=a*c(N+i-1,i)%pr
print(a)

Submission status: Accepted

Solution code:
import collections

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

## 素因数を並べる関数。collections.counterで受ける。
def prime_factorize(K):
    ans = []
    i = 2
    while i ** 2 <= K:
        if K % i == 0:
            K = K//i
            ans.append(i)
        else:
            i += 1
    if K != 1:
        ans.append(K)

    return ans

def combination(N, r):
    ans = N
    mod = pow(10, 9) + 7
    for i in range(1, r):
        ans = ans * ((N - i) % mod) * pow(i + 1, mod - 2, mod)
        ans = ans % mod
    
    return ans
 
prime_nums = dict(collections.Counter(prime_factorize(m)))

ans = 1
mod = pow(10, 9) + 7
for num in prime_nums.values():
    ans = ans * combination(n - 1 + num, num)
    ans = ans % mod

print(ans)

Submission status: Accepted

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

def prime_factorize(K):
    ans = []
    i = 2
    while i ** 2 <= K:
        if K % i == 0:
            K //= i
            ans.append(i)
        else:
            i += 1
    if K != 1:
        ans.append(K)
    
    return ans

def combination(N, r):
    ans = N
    for i in range(1, r):
        ans *= ((N - i) % mod) * pow(i + 1, mod - 2, mod)
        ans %= mod
    
    return ans

prime_nums = dict(collections.Counter(prime_factorize(M)))

ans = 1
for num in prime_nums.values():
    ans *= combination(N - 1 + num, num)
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
def factorize(n):
    from collections import defaultdict
    d = defaultdict(int)
    for i in range(2, int(n**0.5)+1):
        while n%i==0:
            d[i] += 1
            n //= i
        if not n:
            break
    if n>1:
        d[n] += 1
    return d


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

MOD = 10**9+7
n = N+30
fac = [1]*(n+1)
rev = [1]*(n+1)
 
for i in range(1,n+1):
  fac[i] = i*fac[i-1]%MOD
  rev[i] = pow(fac[i], MOD-2, MOD)
 
comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%MOD

v = 1
for i in d.values():
    v *= comb(i+N-1, i)
    v %= MOD
print(v)

Submission status: Accepted

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

MOD = 10 ** 9 + 7
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

for i in range(2, 11**5):
    fact.append((fact[-1] * i) % MOD)
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
    factinv.append((factinv[-1] * inv[-1]) % MOD)

def cmb(n, r):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % MOD

def solve():
    N, M = map(int, input().split())
    l = factorize(M)
    
    ans = 1
    for _, c in l:
        ans = ans * cmb(c+N-1, c) % MOD
        
    return ans

print(solve())

Submission status: Accepted

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

from collections import *

def prime_fact(n):
    prime = Counter()
    m = 0

    while not n % 2: 
        prime[2] += 1
        n //= 2
        m += 1

    x = 3
    while x**2 <= n: 
        c = 0
        while not n % x: 
            prime[x] += 1
            n //= x
            c += 1
        m = max(m, c)
        x += 2

    if n > 1: prime[n] += 1

    return prime, m

MOD = 10**9+7

class Comb:
    def __init__(self, N):
        self.fac = [1] * (N+5)
        for i in range(2, N+5): self.fac[i] = self.fac[i-1] * i % MOD

    def pow(self, a, b):
        res = 1
        while b:
            if b & 1: res = res * a % MOD
            a = a**2 % MOD
            b >>= 1
        return res

    def comb(self, n, r):
        if r < 0 or r > n: return 0
        return (self.fac[n] * self.pow(self.fac[r], MOD-2)) % MOD * self.pow(self.fac[n-r], MOD-2) % MOD

def main():
    N, M = list(map(int, input().split()))
    prime, m = prime_fact(M)

    comb = Comb(N-1+m)
    ans = 1

    for v in prime.values():
        ans = ans * comb.comb(N-1+v, v) % MOD

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