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:
#coding utf-8
import math
from operator import mul
from functools import reduce
N,M=map(int,input().split())

def soinsu(m):
  fact =[]
  i = 2
  while i*i<=m:
    if m%i==0:
      fact.append(i)
      m //=i
    else:
      i +=1
  if m>1:
    fact.append(m)
  return fact

fact=soinsu(M)
counting=[]
for i in fact:
  counting.append(fact.count(i))
  del fact[:fact.count(i)-1]
  if fact==[]:
    break

def combi(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

ans = 1
for i in counting:
  ans *=combi(i+N-1,N-1)

print(ans%(10**9+7))

Submission status: Accepted

Solution code:
import copy
import math
import collections

inf = (10 ** 9) + 7
n, m = map(int, input().split())
prime_dict = {}
m_copy = copy.deepcopy(m)
while (m_copy % 2 == 0):
    m_copy = int(m_copy // 2)
    if 2 not in prime_dict.keys():
        prime_dict[2] = 1
    else:
        prime_dict[2] += 1
for i in range(3, int(math.sqrt(m)) + 1, 2):
    while (m_copy % i == 0):
        m_copy = int(m_copy // i)
        if i not in prime_dict.keys():
            prime_dict[i] = 1
        else:
            prime_dict[i] += 1
if m_copy != 1:
    if m_copy not in prime_dict.keys():
        prime_dict[m_copy] = 1
    else:
        prime_dict[m_copy] += 1
b = list(prime_dict.values())
ans = 1

dp = [[1 for _ in range(30)] for _ in range(n)]
for i in range(1, 30):
    for j in range(1,n):
        dp[j][i] = (dp[j - 1][i] + dp[j][i - 1]) % inf

for bb in b:
    ans *= dp[n - 1][bb]
    ans = ans % inf
print(ans)

Submission status: Accepted

Solution code:
import math
N, M = map(int, input().split())
mod = int(1E9+7)

def prime(n):
    factor = {}
    tmp = int(math.sqrt(n)) + 1
    for num in range(2, tmp):
        while n % num == 0:
            n //= num
            if not num in factor.keys():
                factor[num] = 1
            else:
                factor[num] += 1
    if n != 1:
        if not n in factor.keys():
            factor[n] = 1
        else:
            factor[n] += 1
    return factor

dp = [[1 for _ in range(30)] for _ in range(N)]

for j in range(1, 30):
    for i in range(1, N):
        dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % mod

A = prime(M)

ans = 1
for x in A.values():
    ans *= dp[N-1][x]
    ans = ans % mod
print(ans)

Submission status: Accepted

Solution code:
import math

def cmb(n, r,MOD=10**9+7):
    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]) % MOD
 
    return result % MOD

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

from collections import Counter
def main():
    n,m  = map(int,input().split())
    c = Counter(prime_factorize(m))
    ans = 1
    for i in c.values():
        ans *= cmb(n+i-1,i)
        ans %= 10**9+7
    print(ans%(10**9+7))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections
import sys

def primes(n):
  is_prime=[True]*(n+1)
  is_prime[0]=False
  is_prime[1]=False
  for i in range(2,int(n**0.5)+1):
    if not is_prime[i]:
      continue
    for j in range(i*2,n+1,i):
      is_prime[j]=False
  return [i for i in range(n+1) if is_prime[i]]

def fact(n):
  l=primes(int(n**0.5)+1)
  L=[]
  for i in range(len(l)):
    while n%l[i]==0:
      n=n//l[i]
      L.append(l[i])
    if n==1:
      break
  if n!=1:
    L.append(n)
  return L

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

n,M=map(int,input().split())
if M==1:
  print(1)
  sys.exit()
m=10**9+7
x=list(collections.Counter(fact(M)).values())

g1=[1,1]
g2=[1,1]
inverse=[0,1]

for i in range(2,max(x)+n):
  g1.append((g1[-1]*i)%m)
  inverse.append((-inverse[m%i]*(m//i))%m)
  g2.append((g2[-1]*inverse[-1])%m)

ans=1

for i in range(len(x)):
  ans*=cmb(x[i]+n-1,x[i],m)
  ans%=m
print(ans)

Submission status: Accepted

Solution code:
import collections
from functools import reduce
from operator import mul


def trial_division(n):
    l = []
    f = 2
    while f * f <= n:
        if n % f == 0:
            l.append(f)
            n //= f
        else:
            f += 1
    if n > 1:
        l.append(n)
    return l


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

c = collections.Counter(trial_division(M))
a = 1
for i in c.values():
    a *= combinations_count(i + N - 1, i)

print(a % (10**9 + 7))

Submission status: Accepted

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

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

C = [1] # (N+K-1, N-1) K=0,1,2,...,30
for k in range(1,31):
    C.append(C[-1]*(k+N-1)//k)

F = {}
f = 2
while f*f<=M and M>1:
    if M%f==0:
        if f in F: F[f] += 1
        else: F[f] = 1
        M//=f
    else:
        f+=1

if M in F: F[M]+=1
else: F[M]=1

d = 1
for f, k in F.items():
    d *= C[k]

print(d%1000000007)

Submission status: Accepted

Solution code:
import math
N,M = list(map(int,input().split(" ")))
MOD = 10 ** 9 + 7
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


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]) % MOD

    return result % MOD

ans = 1
fac = factorize(M)
for temp in fac:
    num = temp[1]
    ans *= cmb(num + N - 1,num)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
import math
N,M = list(map(int,input().split(" ")))
MOD = 10 ** 9 + 7
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

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

ans = 1
fac = factorize(M)
for temp in fac:
    num = temp[1]
    ans *= combinations_count(num + N - 1,N-1)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
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 main():
    n, m = map(int, input().split())
    MOD = 10 ** 9 + 7

    m0 = m
    primes = {}
    p = 2
    rtm = int(m ** 0.5 + 1)
    # prime factorization
    while m0 > 1:
        if m0 % p == 0:
            m0 /= p
            if p in primes:
                primes[p] += 1
            else:
                primes[p] = 1
        else:
            p += 1
        # m is prime
        if rtm <= p:
            primes[1] = 1
            break

    ans = 1
    for _, v in primes.items():
        ans *= cmb(n - 1 + v, v)
        ans %= MOD
    print(ans)


main()

Submission status: Accepted

Solution code:
mod = 1000000007


def modpow(a, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        h = modpow(a, p // 2)
        return h * h % mod
    else:
        return a * modpow(a, p - 1) % mod


def calc(a, b):
    if b > a - b:
        return calc(a, a - b)
    am = 1
    ad = 1
    for i in range(b):
        am *= (a - i)
        ad *= (i + 1)
        am %= mod
        ad %= mod
    return am * modpow(ad, mod - 2) % mod


def main():
    N, M = map(int, input().split())
    res = M
    ans = 1
    i = 2
    while res >= i * i:
        if res % i == 0:
            c = 0
            while res % i == 0:
                c += 1
                res //= i
            ans *= calc(N + c - 1, N - 1)
            ans %= mod
        i += 1
    if res != 1:
        ans *= calc(N, N - 1)
        ans %= mod
    print(ans)


main()

Submission status: Accepted

Solution code:

import math
def primes(x):
    if x < 2:
        return []
    ps = [i for i in range(x)]
    ps[1] = 0
    for p in ps:
        if p > math.sqrt(x): break
        if p == 0: continue
        for np in range(2 * p, x, p):
            ps[np] = 0
    return [p for p in ps if p != 0]


def prime_factors(ps, x):
    pfs = []
    for p in ps:
        i = 0
        while x % p == 0:
            x = x // p
            i += 1
        if i != 0:
            pfs.append((p,i))
    return pfs


def mod_comb(a,b,mod):
    #print(a,b)
    if a-b < b: return mod_comb(a,a-b,mod)
    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
    return (ans_mul * modpow(ans_div, mod-2, mod)) % mod

def modpow(a,b,mod):
    if b == 0: return 1
    if b % 2 == 0:
        h = modpow(a, b//2, mod)
        return (h * h) % mod
    else:
        return (a * modpow(a, b-1, mod)) % mod

if __name__ == '__main__':
    MOD = 1000000007
    words = lambda t : list(map(t, input().split()))
    n,m = words(int)
    ans = 1
    for i in range(2,m):
        if i*i > m:
            break
        cnt = 0
        while m % i == 0:
            m = m // i
            cnt += 1
        #print(i, cnt)
        if cnt != 0:
            ans *= mod_comb(n + cnt - 1,n-1,MOD)
            ans %= MOD
    if m != 1:
        ans *= mod_comb(n,n-1,MOD)
        ans %= MOD

    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from functools import reduce
from operator import mul

MOD = 10 ** 9 + 7

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

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

factors = defaultdict(int)
i = 2
while M > 1 and i * i <= M:
    while M % i == 0:
        M //= i
        factors[i] += 1
    i += 1 if i == 2 else 2
if M > 1:
    factors[M] += 1

ans = 1
for n in factors.values():
    ans *= nCr(N + n - 1, n)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
from functools import reduce
from operator import mul


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


def factorize(n):
    """
    nの値を素因数分解し、素因数とその指数をtupleにまとめたリストを返す
    e.g.
    >>> factorize(20)
    [(2, 2), (5, 1)]
    """
    b = 2
    fct = []
    while b * b <= n:
        cnt = 0
        while n % b == 0:
            cnt += 1
            n //= b
        if cnt > 0:
            fct.append((b, cnt))
        b += 1
    if n > 1:
        fct.append((n, 1))
    return fct


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

# M = 2^9 * 5^7 とすると
# 9個のボールとN-1個の仕切りを並べ替える場合の数　* 7個のボールとN-1個の仕切りを並べ替える場合の数
# = 9+N-1_C_9 * 7+N-1_C_7
# で考えられるはず

ans = 1
for fct, e in factorize(M):
    c = cmb(e + N - 1, e) % MOD
    ans = (ans * c) % MOD
print(ans)

Submission status: Accepted

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

import math
List= []
daburi = []
m = M
i = 2
num = 1
while m > 1:
    if m%i == 0:
        m //= i
        if i in List:
            if num == 1:
                daburi.append(2)
            else:
                daburi[-1] += 1
            num += 1
        else:
            num = 1
        List.append(i)
        i -= 1
    i += 1
    if i > math.sqrt(m) and m > 1:
        if List.count(m) == 1:
            daburi.append(2)
        elif List.count(m) > 1:
            daburi[-1] += 1
        List.append(m)
        m = 0

c = N**(len(List)-sum(daburi))

for k in range(len(daburi)):
    c *= (math.factorial(daburi[k]+N-1)//math.factorial(daburi[k])//math.factorial(N-1))

ans = (int(c))%(10**9+7)
print(ans)

Submission status: Accepted

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

import math
from collections import Counter
N,M = map(int,input().split())
mod = 10**9 + 7

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

def fast(x,n):
    if n == 0:
        return 1
    elif n % 2 == 0:
        return fast(x**2 % mod,n//2) % mod
    elif n % 2:
        return x*fast(x**2 % mod,n//2) % mod
fact = [0]*(200001)
fact[0] = 1
for i in range(200000):
    fact[i+1] = fact[i]*(i+1)
    fact[i+1] %= mod

cnt = list(Counter(factorize(M)).items())
ans = 1
for i,j in cnt:
    ans *= fact[j+N-1]
    ans %= mod
    ans *= fast(fact[j],mod-2)
    ans %= mod
    ans *= fast(fact[N-1],mod-2)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
INF = 10**9+7
inv = {}
inv[0] = 1
inv[1] = 1
def p(x):
    if x in inv:
        return inv[x]
    else:
        inv[x] = ((-1)* p(INF%x) * (INF//x))% INF
        return inv[x]
# n H i
l = [1] * 31
l[1] = n 
for i in range(2,31):
    l[i] = ((n+i-1)*l[i-1]*p(i))%INF
# M を素因数分解
def h(x):
    t = x
    d = {}
    for i in range(2,x):
        if i*i > x:
            break
        if t % i != 0:
            continue
        if t % i == 0:
            ind = 0
            while t % i == 0:
                t = t // i
                ind += 1
            d[i] = ind
    if t != 1:
        d[x] = 1
    return d

res = 1
for i in h(m):
    res = (res *  l[h(m)[i]]) % INF

print(res)

Submission status: Accepted

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

def primeFact(N):
    R = int(N**(0.5)) + 1  # 素数の範囲
    factor = {}  # 素数のリスト
    n = N
    for num in range(2, R):
        factor[num] = 0
        while n % num == 0:
            n //= num
            factor[num] += 1
    if n > 1 :
        factor[n] = 1
    return factor

def dictFilter (filter, dic) :
    return { key : val for key, val in dic.items() if filter(key, val)}

primeCount = dictFilter(lambda key, val : val > 0, primeFact(M))

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

ans = 1
for _, count in primeCount.items() :
    ans *= comb(count + N - 1, count) % MOD

print(ans % MOD)

Submission status: Accepted

Solution code:
from collections import Counter
def find(M):
    fact=[]
    while M>1:
        in1=len(fact)
        for i in range(2,int(M**0.5)+1):
            if M%i==0:
                fact+=[i]
                M=M//i
                break
        in2=len(fact)
        if in1==in2:
            break
    fact+=[M]
    return fact
N,M=list(map(int,input().strip().split(' ')))
dic=Counter(find(M))
fact=[1]
temp=1
MOD=10**9+7
for i in range(1,10**6):
    temp*=i
    temp%=MOD
    fact+=[temp]

if N==1 or M==1:
    print(1)
else:
    ans=1
    for x in dic:
        y=dic[x]
        #bino(N+y-1,y)
        up=fact[N+y-1]
        down=(fact[y]*fact[N-1])%MOD
        ans*=(up*pow(down,MOD-2,MOD))%MOD
        ans%=MOD
    print(ans)

Submission status: Accepted

Solution code:
from functools import reduce
from collections import Counter
MOD = 10 ** 9 + 7
N, M = map(int, input().split())

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(lambda x, y : x * y % MOD, range(n, n - r, -1))
    under = reduce(lambda x, y : x * y % MOD, range(1,r + 1))
    return over * pow(under, MOD - 2, MOD)

C = Counter()
def fct(m):
    if m < 2:
        return 1
    r = m
    for i in range(2, int(m**0.5)+1):
        if m % i == 0:
            r = i
            break
    C.update([r])
    return m // r

m = fct(M)
while m != 1:
    m = fct(m)

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

print(cum)

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    elif n<r: return 0
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under
md=10**9+7

n,m=map(int,input().split())
s=[[0,0]]
for i in range(2,int(m**(0.5)+1)):
  k=0
  frag = 0
  if m%i!=0:
    frag = 1
  while m%i==0:
    m=int(m/i)
    k=k+1
  if frag == 0:
    s.append([i,k])
if m!=1:
  s.append([m,1])
q = [0]*(len(s)-1)
for i in range(1,len(s)):
  q[i-1] = s[i][1]

t = 1
for i in range(len(q)):
  c = cmb(n-1+q[i],q[i])
  t = t*(c%md)
  
print(t%md)

Submission status: Accepted

Solution code:
from collections import defaultdict

mod = 10 ** 9 + 7


def cmb(n, r):
    if n < r:
        return 0  # <-直した
    if r > n - r:
        return cmb(n, n - r)
    if r == 0:
        return 1
    if r == 1:
        return n
    res = f[n]
    res *= invs[r]
    res %= mod
    res *= invs[n - r]
    res %= mod
    return res


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

d = defaultdict(int)

x = M
i = 2
while i * i <= M:
    t = 0
    while x % i == 0:
        x //= i
        t += 1
    if t > 0:
        d[i] = t
    i += 1
if x > 1:  # 同じものを表す変数のうち変化するものとしないものがあるとき、変数入れ違いに気を付ける（M>0でエラー）
    d[x] = 1

max_v = max(d.values())

f = [-1] * (N - 1 + max_v + 1)
f[0] = 1
t = 1
for i in range(1, N - 1 + max_v + 1):
    t *= i
    t %= mod
    f[i] = t

# print(d)

inv = pow(t, mod - 2, mod)
invs = [-1] * (N - 1 + max_v + 1)
invs[N - 1 + max_v] = inv
for i in range(N - 1 + max_v - 1, 0, -1):
    inv *= (i + 1)  # <-直した
    inv %= mod
    invs[i] = inv

ans = 1
for cnt in d.values():
    ans *= cmb(N - 1 + cnt, cnt)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import math
import os
import sys
from collections import Counter
from functools import reduce

from operator import mul

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = list(map(int, sys.stdin.readline().split()))


def get_factors(n):
    """
    素因数分解
    :param int n:
    :rtype: 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 ncr(n, r, mod=None):
    """
    scipy.misc.comb または scipy.special.comb と同じ
    組み合わせの数 nCr
    :param int n:
    :param int r:
    :param int mod: 3 以上の素数であること
    :rtype: int
    """
    if n < r:
        return 0
    r = min(n - r, r)
    if r == 0:
        return 1
    return reduce(mul, range(n, n - r, -1)) // reduce(mul, range(r, 0, -1))


factors = get_factors(M)

ans = 1
for c in Counter(factors).values():
    # N 個の箱から重複ありで c 個選ぶ
    ans = ans * ncr(N + c - 1, c) % MOD
print(ans)

Submission status: Accepted

Solution code:
import bisect
import heapq
import itertools
import math
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = list(map(int, sys.stdin.readline().split()))


def get_factors(n):
    """
    素因数分解
    :param int n:
    :rtype: 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


@lru_cache(maxsize=None)
def mod_inv(a, mod):
    """
    a の逆元
    :param int a:
    :param int mod:
    :return:
    """
    return pow(a, mod - 2, mod)


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


def factorial(n):
    if factorials[n]:
        return factorials[n]
    factorials[n] = math.factorial(n) % MOD
    return factorials[n]


def ncr(n, r, mod=None):
    """
    scipy.misc.comb または scipy.special.comb と同じ
    組み合わせの数 nCr
    :param int n:
    :param int r:
    :param int mod: 3 以上の素数であること
    :rtype: int
    """
    if n < r:
        return 0

    # 何度も呼ぶ場合は最大の n 以下の階乗を事前に計算しておくといい
    if mod:
        return (
                factorial(n)
                * mod_inv(factorial(r), mod)
                * mod_inv(factorial(n - r), mod)
                % mod
        )
    else:
        return math.factorial(n) // math.factorial(r) // math.factorial(n - r)


factors = get_factors(M)

ans = 1
for c in Counter(factors).values():
    # N 個の箱から重複ありで c 個選ぶ
    ans = ans * ncr(N + c - 1, c, MOD) % MOD
print(ans)

Submission status: Accepted

Solution code:
def modpow(a, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        halfP = p // 2
        half = modpow(a, halfP)
        return half * half % mod
    else:
        return a * modpow(a, p-1) % mod

def comb(a, b):
    if b > a - b:
        return comb(a, a-b)
    ansMul = 1
    ansDiv = 1
    for i in range(b):
        ansMul *= a - i
        ansDiv *= i + 1
        ansMul %= mod
        ansDiv %= mod

    ans = ansMul * modpow(ansDiv, mod-2) % mod
    return ans

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

mod = 10 ** 9 + 7
ans = 1
for i in range(2, int(M ** 0.5) + 1):
    cnt = 0
    while M % i == 0:
        M //= i
        cnt += 1
    if cnt:
        ans *= comb(cnt+N-1, N-1)
        ans %= mod
if M != 1:
    ans *= N
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N, M = map(int, input().split())
MOD = 10 ** 9 + 7
prime = defaultdict(int)

for i in range(2, M + 1):
    if i * i > M:
        break
        
    while M % i == 0:
        prime[i] += 1
        M //= i
        
if M != 1:
    prime[M] = 1
    
def comb(n, k):
    ret = 1
    for i in range(1, k + 1):
        ret = ret * (n - i + 1) % MOD
        ret = ret * pow(i, MOD - 2, MOD) % MOD
        
    return ret

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

Submission status: Accepted

Solution code:
import math
def factorize(m):
    fct = []
    b = 2
    while b * b <= m:
        cnt = 0
        while m % b == 0:
            m //= b
            cnt += 1
        if cnt > 0:
            fct.append(cnt)
        b += 1
    if m > 1:
        fct.append(1)
    return fct

def comb(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    else:
        return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))

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

for mf in M_fct:
    #mf[1]個をN通りに分ける→comb(mf[1]+N-1,mf[1])
    ans *= comb(N + mf - 1, mf)
    ans %= 10**9+7
print(ans)

Submission status: Accepted

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

def factorize(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

l=factorize(m)
mod=10**9+7
ans=1

def inv(x):
    return pow(x, mod - 2, mod)
 
cms = 10**5 + 100
cm = [0] * cms
 
def comb_init():
    cm[0] = 1
    for i in range(1, cms):
        cm[i] = cm[i-1] * i % mod
 
def c(a, b):
    return (cm[a] * inv(cm[a-b]) % mod) * inv(cm[b]) % mod

mod=10**9+7
comb_init()

for i,j in l:
    ans*=c(j+n-1,j)
    ans=ans%mod

print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def divisions(n):
    sq = int(math.sqrt(n)+1)
    ss = 30030
    a = [None] * (ss)
    a[0] = 1
    t = 1
    for i in range(2,ss):
        if not a[i] is None:
            continue
        if t * i > ss:
            break
        t *= i
        for j in range(i*2,ss,i):
            a[j] = 1
    a = [i for i in range(t) if a[i] is None]
    d = collections.defaultdict(int)
    for i in a[1:]:
        while n % i == 0:
            n //= i
            d[i] += 1

    for j in range(1,sq//t+2):
        if t*j > n:
            break
        for ii in a:
            i = t*j+ii
            while n % i == 0:
                n //= i
                d[i] += 1

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

    return d

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

cms = 10**5 + 100
cm = [0] * cms

def comb_init():
    cm[0] = 1
    for i in range(1, cms):
        cm[i] = cm[i-1] * i % mod

def comb(a, b):
    return (cm[a] * inv(cm[a-b]) % mod) * inv(cm[b]) % mod

def main():
    n,m = LI()

    comb_init()
    d = divisions(m)
    r = 1
    for v in d.values():
        r *= comb(n+v-1,v)
        r %= mod

    return r


print(main())

Submission status: Accepted

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

MAX = 2*10**5+1
MOD = 10**9+7
fact = [0 for i in range(MAX)]
inv = [0 for i in range(MAX)]
invfact = [0 for i in range(MAX)]

def comb_build(n):
  fact[0] = inv[0] = invfact[0] = 1
  fact[1] = inv[1] = invfact[1] = 1
  for i in range(2, n):
    fact[i] = fact[i-1]*i%MOD
    inv[i] = inv[MOD%i]*(MOD-MOD//i)%MOD
    invfact[i] = invfact[i-1]*inv[i]%MOD

def nCk(n, k):
  if n<k or n<0 or k<0:
    return 0
  return (((fact[n]*invfact[k])%MOD)*invfact[n-k])%MOD

def prime_factor(n):
  from collections import defaultdict
  ret = defaultdict(int)
  for i in range(2, int(n**(1/2))+10):
    while n%i==0:
      ret[i] += 1
      n //= i
  if n!=1:
    ret[n] = 1
  return ret

comb_build(MAX)
ans = 1
for e in prime_factor(m).values():
  ans *= nCk(e+n-1, e)%MOD
print(ans%MOD)

Submission status: Accepted

Solution code:
def pmod(a,b,m):
  ret=1
  while b>0:
    if b&1:
      ret=(ret*a)%m
    a=(a*a)%m
    b=b>>1
  return ret
  
def fmod(n,m):
  ret=1
  for i in range(n,0,-1):
    ret=(ret*i)%m
  return ret

def cmod(n,r,m):
  ret=1
  for i in range(r):
    ret=(ret*(n-i))%m
  return (ret*pmod(fmod(r,m),m-2,m))%m

def div(num):
  ret=[]
  for i in range(2,int(num**0.5)+1):
    if num%i==0:
      ret.append(i)
      num=num//i
      while num%i==0:
        ret.append(i)
        num=num//i
  if num!=1:
    ret.append(num)
  return ret

n,m=map(int,input().split())
MOD=10**9+7
d=div(m)
dic={}
for i in d:
  if i not in dic:
    dic[i]=1
  else:
    dic[i]+=1
ans=1
for i in dic.values():
  ans=(ans*cmod(n-1+i,n-1,MOD))%MOD
print(ans)