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 prime_factorize(n):
    ret = []
    # 小さい素数から順に試し割りしていく
    for i in range(2, int(math.sqrt(n))+1):
        if n % i != 0:
            continue
        e = 0
        while n % i == 0:
            e += 1
            n //= i
        ret += [(i, e)]

    if n != 1:
        ret += [(n, 1)]

    return ret


def extgcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
        g = b
    return x, y, g


def modinv(a, m):
    x, y, g = extgcd(a, m)
    if g != 1:
        print ("[+]Inverse does not exist.")
    else:
        return ((m + x) % m) % m


def calc_comb(n, k, mod):
    if k > n-k:
        return calc_comb(n, n-k, mod)

    ans_mul, ans_div = 1, 1

    for i in range(k):
        ans_mul *= (n-i)
        ans_div *= (i+1)
        ans_mul %= mod
        ans_div %= mod

    return (ans_mul * modinv(ans_div, mod) % mod)


def main():
    N, M = map(int, input().split())
    v = prime_factorize(M)
    MOD = int(10**9+7)
    ans = 1

    for i in v:
        ans *= calc_comb(N+i[1]-1, i[1], MOD)
        ans %= MOD
    print (ans)

main()

Submission status: Accepted

Solution code:
Mod = 10**9+7
inv = [0]*41
inv[1] = 1
for i in range(2,41):
  inv[i] = (-(Mod//i)*inv[Mod%i])%Mod
n,m = map(int,input().split())

primes = []
k = 2
while k*k <= m:
  f = 1
  for p in primes:
    if k%p == 0:
      f = 0
      break
  if f == 1:
    primes += [k]
  k += 1
# print(primes)

d = {}
a = m
for p in primes:
  c = 0
  while a%p == 0:
    c += 1
    a //= p
  if c>0:
    d[p] = c
if a > 1:
  d[a] = 1
# print(d)

s = 1
for k in d.values():
  # print(k)
  t = 1
  for i in range(k):
    t = t*(k+n-1-i)*inv[i+1]%Mod
  s = s*t%Mod
print(s)

Submission status: Accepted

Solution code:
import math

mod = 1000000007

def modinverse(a, m):
    x = 0
    y = 1
    gcd = m
    px = 1
    py = 0
    pgcd = a
    temp = 0

    while gcd > 0:
        quotient = pgcd // gcd

        temp = x
        x = px - quotient * temp
        px = temp

        temp = y
        y = py - quotient * temp
        py = temp

        temp = gcd
        gcd = pgcd - quotient * temp
        pgcd = temp
    if px < 0:
        px += m
    return px

def combination(n, r):
    u = 1
    for i in range(n, n - r, -1):
        u = (u * i) % mod
    d = 1
    for i in range(r, 1, -1):
        d *= i
    inverse = modinverse(d, mod)
    return (u * inverse) % mod
 
 

prime = [2]
N, M = map(int, input().split())   
count = 0
for i in range(3, math.floor(math.sqrt(M)) + 1, 2):
    f = True
    for x in prime:
        if i % x == 0:
            f = False
            break
    if f:
        prime.append(i)

c = [0 for i in range(len(prime))]
num = M
for i in range(len(prime)):
    while num % prime[i] == 0:
        c[i] += 1
        num = num // prime[i]
if num != 1:
    prime.append(num)
    c.append(1)

ans = 1
for i in range(len(prime)):
    if c[i] != 0:
        ans *= combination(c[i] + N - 1, c[i])
        ans %= mod

print(ans)

Submission status: Accepted

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

def prime_decomposition(n):
    i = 2
    table = []
    counter = []
    while i * i <= n:
        count = 0
        while n % i == 0:
            n /= i
            table.append(int(i))
            count += 1
        counter.append(count)
        i += 1
    count = 0
    if n > 1:
        table.append(int(n))
        count += 1
        counter.append(count)
    return table, counter

nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]


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;


table, counter = prime_decomposition(M)
result = 1

for i in counter:
    a = cmb_(int(i)+int(N)-1,int(N)-1)

    result *= a

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

Submission status: Accepted

Solution code:
def prime_factorize(num):
    """
    This function performs prime factorization on the input natural number.
    The result is returned in the form of a dictionary with the prime number as the key
    and its number as the value.
    :param num:
    :return prime_factor: Dictionary with the prime number as the key and its number as the value.
    """
    prime_factor = {}
    i = 2
    while i ** 2 <= num:
        while num % i == 0:
            num //= i
            if i in prime_factor.keys():
                prime_factor[i] += 1
            else:
                prime_factor[i] = 1
        i += 1
    if num > 1:
        prime_factor[num] = 1
    return prime_factor



def combination(n, r):
    r = min(n-r, r)
    result = 1
    for i in range(n, n-r, -1):
        result *= i
    for i in range(1, r+1):
        result //= i
    return result


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

prime_fac = prime_factorize(m)
for v in prime_fac.values():
    r *= combination(v + n - 1, v)
mod = 1000000000 + 7
print(r % mod)

Submission status: Accepted

Solution code:
def prime_factorize(num):
    """
    This function performs prime factorization on the input natural number.
    The result is returned in the form of a dictionary with the prime number as the key
    and its number as the value.
    :param num:
    :return prime_factor: Dictionary with the prime number as the key and its number as the value.
    """
    prime_factor = {}
    i = 2
    while i ** 2 <= num:
        while num % i == 0:
            num //= i
            if i in prime_factor.keys():
                prime_factor[i] += 1
            else:
                prime_factor[i] = 1
        i += 1
    if num > 1:
        prime_factor[num] = 1
    return prime_factor


from math import factorial


def comb(n, r, R):
    if n not in R:
        a = factorial(n)
        R[n] = a
    else:
        a = R[n]

    if n - r not in R:
        b = factorial(n - r)
        R[n - r] = b
    else:
        b = R[n - r]

    if r not in R:
        c = factorial(r)
        R[r] = c
    else:
        c = R[r]
    return a // (b * c)


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

R = dict()
prime_fac = prime_factorize(m)
for v in prime_fac.values():
    r *= comb(v + n - 1, v, R)
mod = 1000000000 + 7
print(r % mod)

Submission status: Accepted

Solution code:
import collections

def factor(m):
    num=m
    s=[]
    i=2
    while i*i<=m:
        if num%i:
            i+=1
        else:
            s.append(i)
            num//=i
    if num!=1:
        s.append(num)
    return s

def conb(n,r):
    r=min(r,n-r)
    N,R=n,r
    if r==1:
        return n
    elif r==0:
        return 1
    else:
        for i in range(1,r):
            N*=n-i
            R*=r-i
        return N//R
	
n,m=map(int,input().split())
a=factor(m)
b=collections.Counter(a)
mod=10**9+7
ans=1
for i in b.values():
    ans=(ans*conb(n+i-1,n-1))%mod
print(ans)

Submission status: Accepted

Solution code:
import collections

def factor(m):
    num=m
    s=[]
    i=2
    while i*i<=m:
        if num%i:
            i+=1
        else:
            s.append(i)
            num//=i
    if num!=1:
        s.append(num)
    return s

def conb(n, r):
	N, R = n, r
	for i in range(1, r):
		N *= n-i
		R *= r-i
	return N // R
	
n,m=map(int,input().split())
a=factor(m)
b=collections.Counter(a)
mod=10**9+7
ans=1
for i in b.values():
    ans=(ans*conb(n+i-1,i))%mod
print(ans)

Submission status: Accepted

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

mod = 10 ** 9 + 7
MAX_N = 10 ** 5 + 100

#階乗
def calc_factorial(max_i):
    factorial = [1] * max_i
    for i in range(1, max_i):
        factorial[i] = (i * factorial[i - 1]) % mod
    return factorial

#素因数分解
def calc_factorization(n):
    factorization = {}
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            factorization[i] = 1
            n = n // i
            while n % i == 0:
                factorization[i] += 1
                n = n // i
    if n > 1:
        factorization[n] = 1
    return factorization

#組み合わせ
def comb(factorial, n, k, mod):
    a = factorial[n] % mod
    b = (factorial[k] * factorial[n - k]) % mod
    b_ = pow(b, mod - 2, mod)
    return (a * b_) % mod

C = calc_factorization(M)
#階乗を計算しておく
factorial = calc_factorial(MAX_N)

res = 1
for c in C.items():
    res *= comb(factorial, (c[1] + N - 1), c[1], mod) #combinations_count(factorial, (c[1] + N - 1), c[1], mod)

print(res % mod)

Submission status: Accepted

Solution code:
MOD = int(1e9) + 7


def countup(N, s):
    dp = [0] * (s+1)
    dp[s] = 1
    for _ in range(N):
        for i in range(s):
            dp[i] = sum(dp[i:s+1]) % MOD
    return dp[0]


def main():
    N, M = map(int, input().split())
    F = {}
    i = 2
    while M > 1:
        while M % i == 0:
            if i not in F:
                F[i] = 0
            F[i] += 1
            M //= i
        i += 1
    retval = 1
    for i in F:
        retval *= countup(N, F[i])
        retval %= MOD
    print(retval)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import collections

def factor(m):
  q = m
  r = []
  i = 2
  while i * i <= m:
    if q % i:
      i += 1
    else:
      r.append(i)
      q //= i
  if q != 1:
    r.append(q)
  return r

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

r = factor(m)
v = collections.Counter(r)
c = 1
for value in v.values():
  temp = 1
  for i in range(value):
    temp *= value + n - 1 - i
  for i in range(value):
    temp //= i + 1
  temp %= p
  c = c * temp % p
print(c)

Submission status: Accepted

Solution code:
import math
from collections import defaultdict

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

def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

pr = prime_factors(m)
di = {}
di = defaultdict(int)
for i in pr:
    while m % i == 0:
        m = m // i
        di[i] += 1

"""def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))"""
mod = 10 ** 9 + 7
MAX_N = 10 ** 5 + 100
factorial = [1] * MAX_N
def calc_factorial():
    for i in range(1, MAX_N):
        factorial[i] = i * factorial[i - 1] % mod

def comb(n, k):
    a = factorial[n] % mod
    b = (factorial[k] * factorial[n - k]) % mod
    b_ = pow(b, mod - 2, mod)
    return (a * b_) % mod


# 階乗を用意
calc_factorial()

ans = 1

for i in di:
    ans = ans * comb(di[i] + n - 1, di[i]) % mod
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

"""
参考：http://drken1215.hatenablog.com/entry/2018/09/23/224100
　　　http://tutuz.hateblo.jp/entry/2018/09/24/121248
・素因数分解と重複組み合わせ
・毎回階乗やると死ぬから階乗と逆元のテーブル作る(忘れてた)
"""

from collections import defaultdict
from math import sqrt

MOD = 10 ** 9 + 7

def fact_prime(num):
    d = defaultdict(int)
    # 終点はルート切り捨て+1
    end = int(sqrt(num)) + 1
    for i in range(2, end+1):
        cnt = 0
        # 素因数分解：小さい方から割れるだけ割って素数をカウント
        while num % i == 0:
            num //= i
            d[i] += 1
        # 1まで来たら終了
        if num == 1:
            break
    # 最後までそのまま来たやつはnumが素数(ただし1^1は1^0なので数に入れない)
    if num != 1:
        d[num] += 1
    return d

# とりあえずv+N-1が収まればいいはず
MAX = 10 ** 5 * 2
# 予め組み合わせ計算に必要な階乗と逆元のテーブルを作っておく
factorial = [1] * (MAX)
factorial[0] = factorial[1] = 1
for i in range(2, MAX):
    factorial[i] = factorial[i-1] * i % MOD

inverse = [1] * (MAX)
# powに第三引数入れると冪乗のmod付計算を高速にやってくれる
inverse[MAX-1] = pow(factorial[MAX-1], MOD-2, MOD)
for i in range(MAX-2, 0, -1):
    # 最後から戻っていくこのループならH+W回powするより処理が速い
    inverse[i] = inverse[i+1] * (i+1) % MOD

# 組み合わせの数
def nCr(n, r):
    # 10C7 = 10C3
    r = min(r, n-r)
    # 分子の計算
    numerator = factorial[n]
    # 分母の計算
    denominator = inverse[r] * inverse[n-r] % MOD
    return numerator * denominator % MOD

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

# d = fact_prime(M)
# print(d)
ans = 1
for k, v in fact_prime(M).items():
    # 重複組み合わせ
    # v個のkとN-1個の仕切りから、v個を並べる(v+N-1個のマスからv個を選び出す組み合わせ)
    ans = (ans * nCr(v+N-1, v)) % MOD
print(ans)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
N, M = [int(_) for _ in input().split()]

MAX_N = 10 ** 5 + 100

factorize_result = {}
def factorization(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            factorize_result[i] = 1
            n = n // i
            while n % i == 0:
                factorize_result[i] += 1
                n = n // i
    if n > 1:
        factorize_result[n] = 1


factorial = [1] * MAX_N
def calc_factorial():
    for i in range(1, MAX_N):
        factorial[i] = i * factorial[i - 1] % mod


def comb(n, k):
    a = factorial[n] % mod
    b = (factorial[k] * factorial[n - k]) % mod
    b_ = pow(b, mod - 2, mod)
    return (a * b_) % mod


# 素因数分解
factorization(M)

# 階乗を用意
calc_factorial()

ans = 1
for k, v in factorize_result.items():
    ans *= comb(N + v - 1, v) % mod

print(ans % mod)

Submission status: Accepted

Solution code:
import math
import copy

####################
def prime_decomposition(n):
  i = 2
  X = {}
  while i * i <= n:
    while n % i == 0:
      n /= i
      if i in X:
        X[i] = X[i] + 1
      else:
        X[i] = 1
    i += 1
  if n > 1:
    X[n] = 1
  return X

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 = list(map(int, input().split()))

X = prime_decomposition(M)
       
sum = 1
for i in X.values():
  sum = (sum * cmb(i + N - 1, i) % 1000000007) % 1000000007
  
print(sum)

Submission status: Accepted

Solution code:
import math
from scipy.misc import comb

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

def factorize(M):
    P = []
    F = []
    for m in range(2, int(math.sqrt(M))+1):
        n = 0
        while M % m == 0:
            M/= m
            n +=1
        if n != 0:
            P.append(m)
            F.append(n)
    if M != 1:
        P.append(M)
        F.append(1)
    return P,F

P, F = factorize(M)

X = 1
for f in F:
    X *= int(comb(N+f-1, f, exact=True))
    X %= int(pow(10,9)+7)

print(X)

Submission status: Accepted

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

N, M = (int(i) for i in input().split())

def soin(N):
	res = []
	i = 2
	while i < round(N**(1/2)) + 3:
		if N%i == 0:
			res.append(i)
			N = N//i
			i = 2
		else:
			i += 1
	if N != 1:
		res.append(N)
	return res

def power(a, b):
	if b == 0:
		return 0
	elif b == 1:
		return a % 1000000007
	elif b % 2 == 0:
		return (power(a, b//2) ** 2) % 1000000007
	else:
		return (power(a, b//2) ** 2 * a) % 1000000007

def divide(a, b):
	return (a * power(b, 1000000005)) % 1000000007

def combination(a, b):
	res = 1
	for i in range(b):
		res *= a - i
		res = res % 1000000007
	for i in range(b):
		res = divide(res, i+1)
	return res
if M == 1:
	res = 1
else:
	L = soin(M)
	cc = 1
	res = 1
	for i in range(len(L) -1):
		if L[i] == L[i+1]:
			cc += 1
		else:
			res *= combination(N + cc -1, cc)
			res = res % 1000000007
			cc = 1
	res *= combination(N+cc -1, cc)
	res = res % 1000000007
print(res)

Submission status: Accepted

Solution code:
def prf(m):
    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
    return pf
def inpl(): return [int(i) for i in input().split()]
def comb(n, k):
    k = min(k, n - k)
    result = 1
    for i in range(n, n - k, -1):
        result *= i
    for i in range(1, k + 1):
        result //= i 
    return result

mod = 10**9+7
N, M = inpl()

ans = 1
for i in prf(M).values():
    ans = ans*comb(N+i-1, i)%mod
print(ans)

Submission status: Accepted

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

from math import sqrt, floor

PRIME = 1000000007

def mul(a, b):
    return (a * b) % PRIME

def div(n, d):
    return int(n / d)

def multiDiv(n, d):
    count = 0

    while n % d == 0:
        count += 1
        n = div(n, d)

    return (n, count)

def factoring(n):
    m = floor(sqrt(n))

    (n, f) = multiDiv(n, 2)
    ret = [f]

    for d in range(3, m+1, 2):
        (n, f) = multiDiv(n, d)
        if (f != 0):
            ret.append(f)

    if n != 1:
        ret.append(1)

    return ret

def pow(base, n):

    if n == 0:
        return 1

    if n % 2 == 0:
        return pow(mul(base, base), div(n, 2))
    else:
        return mul(base, pow(base, n - 1))

def reciprocal(n):
    return pow(n, PRIME - 2)

def com(n, k):
    if k == 0:
        return 1

    if (n - k) < k:
        return com(n, n - k)

    ret = 1

    for i in range(1, k + 1):
        ret = mul(ret, reciprocal(i))

    for i in range(n - k + 1, n + 1):
        ret = mul(ret, i)

    return ret


if __name__ == '__main__':

    line = [int(w) for w in input().split()]
    n = line[0]
    m = line[1]

    fs = factoring(m)

    def fun(x):
        return com(n + x - 1, x)
    cs = [fun(i) for i in fs]

    a = 1
    for i in cs:
        a = mul(a, i)

    print(a)

Submission status: Accepted

Solution code:
# coding: utf8

import math

const = 10 ** 9 + 7

def read_int_n():
    return list(map(int, input().split()))

def comb(n, m):
    return math.factorial(n) // (math.factorial(m) * math.factorial(n - m)) 

def power(x, y):
    """
        ２分累乗法
    """
    if      y == 0      :   return 1
    elif    y == 1      :   return x % const
    elif    y % 2 == 0  :   return power(x, y/2) ** 2 % const
    else                :   return power(x, math.floor(y/2)) ** 2 * x % const

if __name__ == "__main__":
    n, m = read_int_n()
    # mを素因数分解する
    cnts = {}
    for i in range(2, math.ceil(math.sqrt(m)) + 1):
        while m % i == 0:
            if i not in cnts:
                cnts[i] = 1
            else:
                cnts[i] += 1
            m //= i
    else:
        if m > 1:
            if m not in cnts:
                cnts[m] = 1
            else:
                cnts[m] += 1
    ans = 1
    for key, value in cnts.items():
        num = 1
        for i in range(value):
            num *= (n + value - 1 - i)
        num //= math.factorial(value)
        # ans *= comb(value + n - 1, value) % const
        ans *= num % const
        ans = ans % const
    print(ans)

Submission status: Accepted

Solution code:
import math

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

divisor = []
dict = {}

m = M
d = 2
while d*d <= m:
    while m % d == 0:
        m //= d
        dict[d] = dict.get(d, 0) + 1
    d += 1
if m > 1:
    dict[d] = dict.get(m, 0) + 1

C = dict.values()
ret = 1


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

def combinations_count(n, r):
    a = max(r, n-r)
    b = min(r, n-r)
    r = 1
    for i in range(a+1, n+1):
        r *= i
    return r // math.factorial(b)


for c in C:
    ret *= combinations_count(c + N - 1, c)
    ret %= MOD

print(ret)

Submission status: Accepted

Solution code:
import math

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

divisor = []
dict = {}

m = M
d = 2
while m != 1:
    while m % d == 0:
        # divisor.append(d)
        m //= d
        dict[d] = dict.get(d, 0) + 1
    d += 1
C = dict.values()
ret = 1


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

def combinations_count(n, r):
    a = max(r, n-r)
    b = min(r, n-r)
    r = 1
    for i in range(a+1, n+1):
        r *= i
    return r // math.factorial(b)


for c in C:
    ret *= combinations_count(c + N - 1, c)
    ret %= MOD

print(ret)

Submission status: Accepted

Solution code:
from math import *

def Prime_Factorization(M):
    factor_count_list = []
    root_M = int(sqrt(M))

    while root_M > 1:
        root_M = int(sqrt(M))

        for i in range(2, root_M + 1):
            e = 0
            while M % i == 0:
                e += 1
                M = M // i
            if e > 0:
                factor_count_list.append(e)
                break
        else:
            break

    if M > root_M:
        factor_count_list.append(1)

    return factor_count_list

def comb(num_object, num_bar):
    numerator = 1

    for i in range(num_bar):
        numerator = (numerator * (num_object - i))

    return  numerator // factorial(num_bar)

def all_comb(N, factor_count_list):
    ans = 1
    for factor in factor_count_list:
        ans = (ans * comb(factor + N - 1, factor)) % (10 ** 9 + 7)
    return ans

def main():
    N, M = map(int, input().split())
    factor_count_list = Prime_Factorization(M)

    print(all_comb(N, factor_count_list))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from math import floor, sqrt
from collections import Counter

MOD = 10 ** 9 + 7

# xを素因数分解する
def getPrimeFactor(x):
    ans = []
    for d in range(2, floor(sqrt(x)) + 1):
        while x % d == 0:
            ans.append(d)
            x //= d
    if x != 1:
        ans.append(x)
    return ans

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


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

PFs = getPrimeFactor(M)
cnt = Counter(PFs)

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

Submission status: Accepted

Solution code:
def combination(n, r):
    if r > n-r:
        r = n-r
    a = 1
    for i in range(n, n-r, -1):
        a = a * i
    d = 1
    for i in range(1, r+1):
        d = d*i
    return a//d


def generate_prime_map(n):
    m = {}
    b, e = 2, 0
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            m[b] = e
        b, e = b + 1, 0
    if n > 1:
        m[n] = 1
    return m


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

m = generate_prime_map(M)

ans = 1
mod = 10**9+7
for v in m.values():
    ans *= combination(v+N-1, v)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


'''Snippets for prime.
Available functions:
- is_included: Determine whether it is a prime number.
- generate: Generate a list of prime numbers using sieve of Eratosthenes.
'''


class Prime(object):
    '''Represents a snippet for prime numbers.
    '''

    def __init__(self, number):
        self.number = number
        self._values = []

    def is_included(self) -> bool:
        '''Determine whether it is a prime number.
        Args:
            number: Int of number (greater than 0).
        Returns:
            True if the input number was prime.
            False if the input number was not prime.
        See:
            https://qiita.com/srtk86/items/874639e361917e5016d4
            https://docs.python.org/ja/3/library/2to3.html?highlight=isinstance#2to3fixer-isinstance
        '''

        from math import sqrt

        if (self.number <= 1) or (isinstance(self.number, float)):
            return False

        for i in range(2, int(sqrt(self.number)) + 1):
            if self.number % i == 0:
                return False

        return True

    def generate(self) -> list:
        '''Generate a list of prime numbers using sieve of Eratosthenes.
        Returns:
            A list of prime numbers that is eqaul to or less than the input
            number.
        Landau notation: O(n log log n)
        See:
            https://beta.atcoder.jp/contests/abc110/submissions/3254947
        '''

        if self._values:
            return self._values

        is_met = [True for _ in range(self.number + 1)]
        is_met[0] = False
        is_met[1] = False

        for i in range(2, self.number + 1):
            if is_met[i]:
                self._values.append(i)

                for j in range(2 * i, self.number + 1, i):
                    is_met[j] = False
        return self._values


def count_combinations(n, k, mod):
    ans = 1

    for i in range(1, k + 1):
        ans *= n - i + 1
        ans %= mod
        ans *= pow(i, mod - 2, mod)
        ans %= mod

    return ans


def main():
    from math import sqrt

    n, m = map(int, input().split())
    _prime = Prime(int(sqrt(m)) + 1)
    primes = _prime.generate()
    mod = 10 ** 9 + 7
    ans = 1

    for prime in primes:
        count = 0

        while m % prime == 0:
            count += 1
            m //= prime

        ans *= count_combinations(n + count - 1, count, mod)
        ans %= mod

    if m != 1:
        ans *= count_combinations(n, 1, mod)
        ans %= mod

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

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

sqrt_m = math.sqrt(m)
sqrt_m = int(sqrt_m) + 1

mod = 10**9 + 7
fac = [1, 1]
inv = [1, 1]
finv = [1, 1]
for i in range(2, n + 31):
    fac.append(fac[i-1] * i % mod)
    inv.append(mod - inv[mod%i] * (mod//i) % mod)
    finv.append(finv[i-1] * inv[i] % mod)

def nck(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod


prime = []
for i in range(2, sqrt_m + 1):
    count = 0
    while m % i == 0:
        m = m // i
        count += 1
    if count > 0:
        prime.append(count)
if m > 1:
    prime.append(1)

ans = 1
for i in prime:
    ans *= nck(n-1+i, i)
    ans %= mod

print(ans)

Submission status: Accepted

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

import math 
L=math.floor(math.sqrt(M))

X=dict()

for i in range(2,L+2):
    while M%i==0:
        X[i]=X.get(i,0)+1
        M=M//i

if M!=1:
    X[M]=X.get(M,0)+1
    


def Combi2(a,b):#aは大きいが、bは小さいとき
    if b>a:
        return 0
    ANS=1
    for i in range(min(b,a-b)):
        ANS=ANS*(a-i)*pow(min(b,a-b)-i,mod-2,mod)

    return ANS%mod

ANS=1
for x in X.values():
    ANS=(ANS*Combi2(x+N-1,x))%mod

print(ANS)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import Counter

def factorize(n: int):
    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

# nの逆元のリスト
def inv_mod(n:int, mod:int) -> list:
    inv = [0,1]
    for i in range(2,n+1):
        inv.append(mod - ((mod//i)*inv[mod%i]) % mod)
    return inv
       
# nの階乗のリスト
def fact(n:int, mod:int) -> list:
    fac = [1,1]
    res = 1
    for i in range(2,n+1):
        res = res*i%mod
        fac.append(res)
    return fac

# nの階乗の逆元のリスト
def fact_inv(n:int, inv:list, mod:int) -> list:
    facInv = [1,1]
    for i in range(2,n+1):
        facInv.append(facInv[i-1]*inv[i] % mod)
    return facInv
        
# 二項係数
def nCr(n:int, r:int, mod:int, fac:list, facInv:list) -> int:
    if not (0<=r and r<=n):
        return 0
    
    return ((fac[n]*facInv[r]) % mod) * facInv[n-r] % mod

# 重複組み合わせ
def nHr(n:int, r:int, mod:int, fac:list, facInv:list) -> int:
    if r<0 or n<0:
        return 0
    
    else:
        return nCr(n+r-1,r,mod,fac,facInv)

n,m = li()
MOD = 10**9+7

inv = inv_mod(2*10**5, MOD)
fac = fact(2*10**5, MOD)
facinv = fact_inv(2*10**5,inv,MOD)

md = factorize(m)

ans = 1
for k,v in md.items():
    ans *= nHr(n,v,MOD,fac,facinv)
    ans %= MOD
    
print(ans)

Submission status: Accepted

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

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

MAXN = N+99
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)

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math

# 高速 組み合わせ
def C(n, r):
  a = 1
  b = 1
  for i in range(r):
    a = a*(n-i)
    b = b*(r-i)
  return((a//b))

from collections import Counter

N, M = map(int, input().split())
D = 1000000000 + 7

def primes(n):
    primfac = []
    d = 2
    while d*d <= n:
        while (n % d) == 0:
            primfac.append(d)  # supposing you want multiple factors repeated
            n //= d
        d += 1
    if n > 1:
       primfac.append(n)
    return primfac


f = primes(M)
cntr = Counter(f)

ans = 1
for k,v in cntr.items():
    ans *= C(v+N-1,v) %D

print(ans%D)

Submission status: Accepted

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

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

MOD = 10**9+7

MAX = 2*10**5

fac = [1,1] + [0]*MAX
finv = [1,1] + [0]*MAX
inv = [0,1] + [0]*MAX
for i in range(2,MAX+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)


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