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:
N,M=map(int,input().split())
a=[]
ans=1
def calc(n):#nの素因数分解
    for i in range(2,int(n**0.5)+10):
        count=0
        while n%i==0:
            n//=i
            count+=1
        if count>=1:
            a.append([i,count])
    if n!=1:
        a.append([n,1])
calc(M)
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
for i in range(len(a)):
    ans*=cmb(a[i][1]+N-1,a[i][1])
print(ans%(10**9+7))

Submission status: Accepted

Solution code:
from collections import defaultdict

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

MOD = 1000000007

#階乗、逆元のテーブル算出。0番目は未使用
TABLE_NUM = 10001 + N
facts = [0 for _ in range(TABLE_NUM)]
invs = [0 for _ in range(TABLE_NUM)]
finvs = [0 for _ in range(TABLE_NUM)]
def create_table():
    facts[0] = facts[1] = 1
    invs[0] = invs[1] = 1
    finvs[0] = finvs[1] = 1
    for i in range(2, TABLE_NUM):
        facts[i] = facts[i - 1] * i % MOD
        invs[i] = MOD - invs[MOD % i] * (MOD // i) % MOD
        finvs[i] = finvs[i - 1] * invs[i] % MOD
create_table()

def comb(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return facts[n] * (finvs[k] * finvs[n - k] % MOD) % MOD


#素因数分解
prime_dict = defaultdict(int)
primes = []
n = 2
m = M
M_ROOT = int(M ** 0.5)
while m > 1 and n <= M_ROOT:
    if m % n == 0:
        prime_dict[n] += 1
        primes.append(n)
        m = m // n
        continue
    n += 1

if m > M_ROOT:
    primes.append(m)
    prime_dict[m] += 1

# n = 素数の乗数合計
# r = 素数自体の数
# Ai = Pi0 ** bi0 * Pi1 ** bi1 **  ...
# A0のパターン = nCr
# A1のパターン =

ans = 1
for k in prime_dict.keys():
    v = prime_dict[k]
    count = comb(v + N - 1, N - 1)
    ans = (ans * count) % MOD
print(ans)

Submission status: Accepted

Solution code:
# 素数リスト生成
def sieve(x):
    if x < 2: return []
    primes = [i for i in range(x)]
    primes[1] = 0
    for p in primes:
        if p > x ** (1/2): break
        if p == 0: continue
        for np in range(2 * p, x, p): primes[np] = 0
    return [p for p in primes if p != 0]

PS = sieve(10**6)

# 素因数分解
def factorint(x):
  d = {}
  for k in PS:
    if(x % k== 0):
      m = 1
      while(x % (k**m) == 0):
        m += 1
      d[k] = m - 1
      x = x / (k ** (m - 1))
      if x == 1:
        break
  return d

n, m = map(int, input().split())
f = factorint(m)
idx = [i for i in f.values()]
# 10^6より大きい素因数があったときの処理
re = 1
for k, v in f.items():
  re *= k**v
if m // re != 1:
  idx.append(1)


def fact(n):
  ret = 1
  for i in range(1, n + 1):
    ret *= i
  return ret
def com(n, r):
  if n - r < r: r = n - r
  ret = 1
  for i in range(n-r+1, n+1):
    ret *= i
  for j in range(1, r+1):
    ret //= j
  return ret

ans = 1
for i in range(len(idx)):
  ans *= com(idx[i] + n - 1, n - 1) % (10 ** 9 + 7)

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

Submission status: Accepted

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

def prime_decomposition(n):
    p = 2
    prime = {}
    while n!=1:
        while n%p == 0:
            n = n//p
            if p not in prime:
                prime[p] = 0
            prime[p] += 1
        p += 1
    return prime

primes = prime_decomposition(m)
# print(primes)
ans = 1

def combination(n,k):
    ret1 = 1
    ret2 = 1
    for i in range(k):
        ret1 *= n-i
        ret2 *= k-i
    return ret1//ret2

for pw in primes.values():
    comb = combination(pw+n-1, pw)
    ans *= comb
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
rM=M**(1/2)
MOD=10**9+7
i=2
s=0
ans=1
while i<=rM:
  if M%i==0:
    M=M//i
    s+=1
  elif s!=0:
    comb=1
    for j in range(s+N-1,N-1,-1):
      comb*=j
    for j in range(s,0,-1):
      comb//=j
    ans*=comb
    ans%=MOD
    i+=1
    s=0
  else:
    i+=1
if M!=1:
  ans*=N
  ans%=MOD
print(ans)

Submission status: Accepted

Solution code:
def prime_factorize(num):
    # 整数に対し素因数分解
    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):
    # nCrを求める
    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())
MOD = 10**9 + 7
P = prime_factorize(m)
ans = 1
for prime in P:
    k = combination(P[prime] + n - 1, P[prime]) % MOD
    ans *= k
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
from math import sqrt


def prime_facts(n: int) -> dict:
    res = {}
    d = 2
    while d * d <= n:
        if n % d == 0:
            res[d] = 1
            n //= d

            while n % d == 0:
                res[d] += 1
                n //= d

        if d == 2:
            d += 1
        else:
            d += 2

    if n > 1:
        res[n] = 1

    return res


def factorization(N: int, M: int) -> int:
    """以下の説明において、F(N, M) はこの関数と同値。

    `a1 x a2 x ... x aN = M (式 1)`
    となる数列 {aN} の組み合わせ数を F(N, M) とする。

    まず、(式 1)より {aN} は全て M の約数であることは明らか。

    ここで、M の約数列を {dm} とする。今、aN = di とすると、
    `a1 x a2 x ... x a{N-1} = M // di`
    が成り立ち、これを満たす数列 {a{N-1}} の組み合わせ数は F(N-1, M//di) である。

    aN は任意の di を取れるので、結局、
    `F(N, M) = sigma{di} F(N-1, M//di) = sigma{di} F(N-1, M)` (式 2)
    が成り立つ。

    さらに、M を場合分けして考える。

    M = 1 のとき、(式 2)より
    `F(N, 1) = F(N-1, 1) = ... = F(1, 1) = 1` (式 3)
    が成り立つ。

    M = p (p は素数)のとき、(式 2)と(式 3)より、
    `F(N, p) = F(N-1, p) + F(N-1, 1) = F(N-1, p) + 1`
    が成り立つ。この漸化式をとけば、
    `F(N, p) = N`
    が成り立つ。

    M = p^k (p は素数)の時、めんどくさい計算の果てに
    `F(N, p^k) = PI{i=0}{k-1}(N+i) / k!`
    が成り立つ。

    M = p1...pk (pi は全て異なる素数)の時、めんどくさい計算の果てに
    `F(N,p1...pk) = N^k`

    M = p1^k1 ... pm^km (pi は全て異なる素数)の時、めんどくさい計算の果てに
    `F(N,p1^k1...pm^km) = F(N,p1^k1)...F(N,pm^km)`
    が成り立つ。
    """
    # pi と fact の初期化
    pi = [1] * 101
    fact = [1] * 101
    for i in range(1, 101):
        pi[i] = (N+i-1) * pi[i-1]
        fact[i] = i * fact[i-1]

    primes = prime_facts(M)
    ret = 1
    for k in primes.values():
        ret *= pi[k] // fact[k]

    return ret % 1000000007


if __name__ == "__main__":
    N, M = map(int, input().split())
    ans = factorization(N, M)
    print(ans)

Submission status: Accepted

Solution code:
ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))
rr = lambda N: [ri() for _ in range(N)]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18

N,M=rl()
DIV = 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

l = factorize(M)

ans = 1
for _, i in l:
    res = 1
    for j in range(i):
        res *=(N-1+i-j)
    for j in range(i):
        res = res//(j+1)
    ans *= res
    ans %= DIV

print(ans)

Submission status: Accepted

Solution code:
ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))
rr = lambda N: [ri() for _ in range(N)]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18

N,M=rl()
DIV = 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

l = factorize(M)

ans = 1
for _, i in l:
    res = 1
    for j in range(i):
        res *=(N-1+i-j)%DIV
    for j in range(i):
        res = res//(j+1)
    ans *= res
    ans %= DIV

print(ans)

Submission status: Accepted

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

import math
import random
from itertools import permutations, combinations

class Prime:
    seed_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

    def is_prime(self, n):
        """
        prime test (hybrid)

        see also: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369

        :param n:
        :return: boolean
        """
        is_prime_common = self.is_prime_common(n)
        if is_prime_common is not None:
            return is_prime_common

        if n < 2000000:
            return self.is_prime_brute_force(n)
        else:
            return self.is_prime_miller_rabin(n)

    def is_prime_common(self, n):
        if n == 1: return False
        if n in Prime.seed_primes: return True
        if any(map(lambda x: n % x == 0, self.seed_primes)): return False

    def is_prime_brute_force(self, n):
        """
        brute force prime test
        use with is_prime_common if you want to skip seed_primes

        :param n:
        :return: boolean
        """
        for k in range(2, int(math.sqrt(n)) + 1):
            if n % k == 0:
                return False
        return True

    def is_prime_miller_rabin(self, n):
        """
        miller rabin prime test
        use with is_prime_common if you want to skip seed_primes

        see also
            algorithm: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
            implementation: https://qiita.com/srtk86/items/609737d50c9ef5f5dc59
            improvement: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369

        :param n:
        :return: boolean
        """

        d = n - 1
        while d & 1 == 0:
            d >>= 1

        # use one of these lines / upper is more efficient.
        witnesses = self.get_witnesses(n)
        # witnesses = [random.randint(1, n - 1) for _ in range(100)]

        for w in witnesses:
            y = pow(w, d, n)

            while d != n - 1 and y != 1 and y != n - 1:
                y = (y * y) % n
                d <<= 1

            if y != n - 1 and d & 1 == 0:
                return False

        return True

    def get_witnesses(self, num):
        def _get_range(num):
            if num < 2047:
                return 1
            if num < 1373653:
                return 2
            if num < 25326001:
                return 3
            if num < 3215031751:
                return 4
            if num < 2152302898747:
                return 5
            if num < 3474749660383:
                return 6
            if num < 341550071728321:
                return 7
            if num < 3825123056546413051:
                return 9
            return 12

        return self.seed_primes[:_get_range(num)]

    def gcd(self, a, b):
        if a < b:
            return self.gcd(b, a)
        if b == 0:
            return a
        while b:
            a, b = b, a % b
        return a

    @staticmethod
    def f(x, n, seed):
        """
        pseudo prime generator
        :param x:
        :param n:
        :param seed:
        :return: pseudo prime
        """
        p = Prime.seed_primes[seed % len(Prime.seed_primes)]
        return (p * x + seed) % n

    def find_factor(self, n, seed=1):
        """
        find one of factor of n
        this function is based to Pollard's rho algorithm

        see also
            algorithm: https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
            implementation: https://qiita.com/gushwell/items/561afde2e00bf3380c98

        :param n:
        :param seed:
        :return: factor
        """
        if self.is_prime(n):
            return n

        x, y, d = 2, 2, 1
        count = 0
        while d == 1:
            count += 1
            x = self.f(x, n, seed)
            y = self.f(self.f(y, n, seed), n, seed)
            d = self.gcd(abs(x - y), n)

        if d == n:
            return self.find_factor(n, seed+1)
        return self.find_factor(d)

    def find_factors(self, n):
        primes = {}
        if self.is_prime(n):
            primes[n] = 1
            return primes

        while n > 1:
            factor = self.find_factor(n)

            primes.setdefault(factor, 0)
            primes[factor] += 1

            n //= factor

        return primes


prime = Prime()
fact_dict = prime.find_factors(M)

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

result = 1
for val in fact_dict.values():
    result *= cmb(N + val - 1, val)
print(result % (10**9+7))

Submission status: Accepted

Solution code:
from collections import defaultdict
MOD = 10**9 + 7

def Mod_Power(a, n, mod):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res

def Mod_Inverse(a, mod):
    return Mod_Power(a, mod-2, mod)

def Mod_Combination(n, k, mod):
    p, q = 1, 1
    for i in range(n-k+1, n+1):
        p = (p * i) % mod
    for i in range(2, k+1):
        q = (q * i) % mod
    return int(p * Mod_Inverse(q, mod) % mod)

N, M = map(int, input().split())
prime_factors = defaultdict(int)
i, L = 2, M
while True:
    while L % i == 0:
        L /= i
        prime_factors[i] += 1
    if L == 1 or i * i > M:
        break
    i += 1
if L > 1:
    prime_factors[L] = 1
res = 1
for key in prime_factors:
    res = res * Mod_Combination(prime_factors[key] + N - 1, N - 1, MOD) % MOD
print(int(res))

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

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

C = [[0 for i in range(40)] for j in range(n+40)]

def genprime(nnn):
    prime = [2,3]
    for i in range(5,nnn):
        f = True
        for p in prime:
            if(p*p > i):break
            if i % p == 0 :
                f = False
                break
        if f :prime.append(i)
    return prime

C[1][0],C[1][1] = 1,1
for i in range(2,n+40):
    for j in range(min((i+1),40)):
        if(i == j):
            C[i][i] = 1
            continue
        if(j == 0):
            C[i][j] = 1
            continue
        C[i][j] = (C[i-1][j-1]+C[i-1][j]) % MOD

prime = genprime(100000)

cnt = [0 for i in range(len(prime))]

for k,pp in enumerate(prime):
    while(m % pp == 0):
        m //= pp
        cnt[k] += 1
if(m == 1): ans = 1
else: ans = n
for k,pp in enumerate(cnt):
    if pp == 0:continue
    ans = (ans *C[pp+n-1][pp]) % MOD

print(ans)

Submission status: Accepted

Solution code:
import math

def prime_division(n):
    ans = []
    m = int(n ** 0.5)
    i = 2
    while i <= m:
        if n % i == 0:
            cnt = 0
            while n % i == 0:
                n //= i
                cnt += 1
            ans.append((i, cnt))
            m = int(n ** 0.5)
        i += 1
    if n != 1:
        ans.append((n, 1))
    return ans

def combination(n, r):
    ans = 1
    if n - r < r:
        r = n - r
    for i in range(r):
        ans *= n - i
    ans //= math.factorial(r)
    return ans

#  aabaaba  count+(N-1) C (N-1)

N,M=map(int,input().split())
pms=prime_division(M)
ans = 1
for pm in pms:
    #print(pm)
    ans *= combination(pm[1]+(N-1), N-1)

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

Submission status: Accepted

Solution code:
import math


def get_primes(n):
    primes = []
    checks = [True for _ in range(int(math.sqrt(n)) + 1)]
    checks[0] = checks[1] = False
    for i in range(2, len(checks)):
        if checks[i]:
            primes.append(i)
            tmp = 0
            while i + tmp * i < len(checks):
                checks[i + tmp * i] = False
                tmp += 1
    return primes


def combination(a, b):
    i = 1
    for _i in range(a - b + 1, a + 1):
        i *= _i
    return i // math.factorial(b)


def solve(string):
    n, m = map(int, string.split())
    primes = get_primes(m)
    m_copy = m
    divides = dict()
    for _p in primes:
        while m_copy % _p == 0:
            m_copy = m_copy // _p
            if str(_p) in divides.keys():
                divides[str(_p)] += 1
            else:
                divides[str(_p)] = 1
    if m_copy > 1:
        divides[str(m_copy)] = 1

    ans = 1
    for i in divides.values():
        ans *= combination(i + n - 1, i)
    return str(ans % (1000000007))


if __name__ == '__main__':
    print(solve(input()))

Submission status: Accepted

Solution code:
import math

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

def kai(n):
    return math.factorial(n)

def H(n, r):
    rtn = 1
    for i in range(n+r-1, n-1, -1):
        rtn *= i
    rtn //= kai(r)
    return rtn


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

prime = prime_factor2(M)

ans = 1
mili = (10**9 + 7)
for v in prime.values():
    h = H(N, v) % mili
    ans  =  ans * h

ans = ans % mili
ans = int(ans)
print(ans)

Submission status: Accepted

Solution code:
import math

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

def kai(n):
    return math.factorial(n)

def H(n, r):
    rtn = 1
    for i in range(n+r-1, n-1, -1):
        rtn *= i
    rtn //= kai(r)
    return rtn


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

prime = prime_factor2(M)

ans = 1
for v in prime.values():
    h = H(N, v) % (10**9 + 7)
    ans  =  ans * h

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

Submission status: Accepted

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


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


# 重複組み合わせ
def nHk(n, k):
    value = 1
    nk = n + k - 1
    k = min(nk-k, k)
    for i in range(k):
        value = (value * nk) % mod
        nk -= 1
    for x in range(1, k + 1):
        value = (value * pow(x, mod-2, mod)) % mod
    return value


T = prime_factorization(M)
C = Counter(T)

ans = 1
for v in C.values():
    ans *= nHk(N, v)
    ans %= mod

print(ans)

Submission status: Accepted

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

def fact(m):
    c = Counter()
    s = 2
    while s**2 <= m:
        if m % s:
            s += 1
            continue
        while m % s == 0:
            c[s] += 1
            m //= s
    if m > 1:
        c[m] += 1
    return c

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

ans = 1
for cnt in fact(m).values():
    ans = ans*comb(cnt+n-1, cnt) % mod
#    for i in range(cnt):
#        ans = ans*(cnt+n-1-i)//(i+1)
print(ans % mod)

Submission status: Accepted

Solution code:
mod = 10**9 + 7

def factorize(n):
    # http://nihaoshijie.hatenadiary.jp/entry/2018/02/03/115759
    fct = []
    b, e = 2, 0
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append(e)
        b, e = b + 1, 0
    if n > 1:
        fct.append(1)
    return fct

class COMB_MOD():
    # http://drken1215.hatenablog.com/entry/2018/06/08/210000
    def __init__(self, max_n=510000, mod=10**9+7):
        self.fac = [0]*max_n
        self.finv = [0]*max_n
        self.inv = [0]*max_n
        self.fac[0] = self.fac[1] = 1
        self.finv[0] = self.finv[1] = 1
        self.inv[1] = 1
        self.max = max_n
        self.mod = mod
        self._maesyori()

    def _maesyori(self):
        for i in range(2,self.max):
            self.fac[i] = self.fac[i-1] * i % self.mod
            self.inv[i] = self.mod - self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.finv[i] = self.finv[i-1] * self.inv[i] % self.mod

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

n, m = map(int,input().split())
fct = factorize(m)
ans = 1
COM = COMB_MOD()
for cnt in fct:
    ans = ans*COM.COM(cnt+n-1, cnt) % mod
print(ans)

Submission status: Accepted

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

i = 2
counts = []
while i**2 <= m:
    c = 0
    while m%i == 0:
        m //= i
        c += 1
    if c > 0:
        counts.append(c)
    i += 1
if m > 1:
    counts.append(1)

def combi(p, r):
    f = 1
    r = min(r, p-r)
    for i in range(r):
        f *= (p-i)
        f //= (i+1)
    return f

ans = 1
for c in counts:
    ans = (ans * combi(c+n-1, c))%MOD
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
MAX_PRIME = 10 ** 5
is_prime = [1] * MAX_PRIME
primes = []
is_prime[0] = 0
is_prime[1] = 0
for i in range(MAX_PRIME):
    if is_prime[i]:
        primes.append(i)
        for j in range(2, MAX_PRIME // i):
            is_prime[i*j] = 0
def fact(m):
    ret = {}
    for p in primes:
        if p * p > m:
            if m != 1:
                ret[m] = 1
            return ret
        while(m % p == 0):
            if p not in ret:
                ret[p] = 1
            else:
                ret[p] += 1
            m //= p
def c(n,i):
    child = 1
    parent = 1
    k = n - 1 + i
    for j in range(1,i+1):
        parent *= j
        child *= k - j + 1
    return child // parent
factors = fact(m)
ret = 1
for _, power in factors.items():
    ret *= c(n,power)
    ret %= 10 ** 9 + 7
print(ret)

Submission status: Accepted

Solution code:
from collections import Counter
import math
n,m = map(int, input().split())
def combinations_count(n, r):
    l = 1
    for num in range(1,r+1):
      l *= (n+num)
      l = l // num
    return l
def prime_decomposition(n, table):
    i = 2
    while i * i <= n:
        while n % i == 0:
            n /= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
table = []
prime_decomposition(m, table)
c = Counter(table).values()
cc = Counter(c)
ans = 1
N = n-1
for i,j in cc.items():
  ans *= ((combinations_count(N,i))**j)%(10**9+7)
print(ans%(10**9+7))

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce

def comb(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= [int(i) for i in input().split(" ")]

c = []
i = 2
mt = m

while i * i <= mt:
    ci = 0
    while mt % i == 0:
        mt = mt // i
        ci += 1
    if ci > 0:
        c.append(ci)
    i += 1
if mt > 1:
    c.append(1)
    
p = 1
for j in range(0, len(c)):
    p *= comb(n - 1 + c[j], c[j])

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

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 fctr1(n): 
    f=[]
    c=0
    r=int(n**0.5)
    for i in range(2,r+2):
        while n%i==0:
            c+=1
            n=n//i
        if c!=0:
            f.append([i,c])
            c=0
    if n!=1:
        f.append([n,1])
    return f

n, m = map(int,input().split())
MOD, ans = 10**9+7, 1
c = fctr1(m)
for i in c:
    ans = ans*cmb(i[1]+n-1,n-1)%MOD
print(ans)

Submission status: Accepted

Solution code:
def memorize(func):
    memo = {}
    def wrapper(*args):
        if args not in memo:
            memo[args] = func(*args)
        return memo[args]
    return wrapper
def factorize(n, factor=2, index=0):
    counter = 0
    while True:
        if n%factor==0:
            n //=factor
            counter += 1
        else:
            break
    if counter>0:
        yield (factor, counter)
    if factor**2 < n:
        yield from factorize(n, factor+1)
    elif n>2:
        yield (n, 1)
@memorize
def choose(N, M):
    if M>N:
        return 0
    if N==0 or M==0:
        return 1
    else:
        return N*choose(N-1, M-1)//M
def ans(N, M):
    val = 1
    for _, r in factorize(M):
        val *= choose(N+r-1, r)
        val %= (10**9+7)
    return val
import sys; sys.setrecursionlimit(100000)
print(ans(*map(int, input().split())))

Submission status: Accepted

Solution code:
import math
def comb(x,y):
    f = 1
    for i in range(y):
        f *= (x-i)
        f //= (i+1)

    return f

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

i = 2
cnt = []
while i*i<=m:
    c = 0
    while m%i == 0:
        m //= i
        c += 1
    if c>0:
        cnt.append(c)
    i+=1
if m>1:
    cnt.append(1)
        

res = 1
r = 10**9 +7
for item in cnt:
    res = (res* comb(item+n-1,item))%r

print(res%r)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc110/tasks/abc110_d


def get_prime_dic(n):
    dic = {}

    i = 2
    while i * i <= n:
        while n % i == 0:
            n //= i
            if i in dic:
                dic[i] += 1
            else:
                dic[i] = 1
        i += 1

    if n > 1:
        dic[n] = 1
    return dic


# Calculate count of combination
def combination(n, r):
    a = 1
    b = 1
    for i in range(r):
        a *= (n - i)
        b *= (i + 1)
    return a // b


def main():
    N, M = map(int, input().split())
    d = get_prime_dic(M)
    # print(d)

    ans = 1
    for k, v in d.items():
        ans *= combination(v + N - 1, v)
        ans %= 1000000007

    print(ans)


main()

Submission status: Accepted

Solution code:
N, M = [int(i) for i in input().split()]
mod = 10 ** 9 + 7
def func(M):
  res = []
  i = 2
  while i * i <= M:
    c=0
    while M % i == 0:
      M /= i
      c += 1
    if c > 0:
      res.append(c)
    i += 1
  if M > 1:
    res.append(1)
  return res

def conb(n, r):
  N, R = n, r
  for i in range(1, r):
    N *= n-i
    R *= r-i
  return N // R

res = func(M)
ans = 1
for i in res:
  ans = (ans * conb(i+N-1, i)) % mod
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict


def combination(n, r):
    ret = 1
    a = 1
    b = 1
    for i in range(1,r+1):
        a *= (n+i-1)
        b *= (r-i+1)
    return a // b


def compute_divisors(n):
    ret = defaultdict(int)
    m = n
    while m%2 == 0:
        ret[2] += 1
        m = m//2
    r = 3
    while m > 1:
        if r**2 > m:
            ret[m] = 1
            break
        while m%r==0:
            ret[r] += 1
            m = m//r
        r += 2
    return ret


def main():
    N, M = list(map(int, input().split(' ')))
    divisors = compute_divisors(M)
    exp = 0
    ret = 1
    for d in divisors:
        c = divisors[d]
        ret *= combination(N,c)
        ret %= 1000000007
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
memo={}
def primes(n):
    primefac = []
    d = 2
    while d*d <= n:
        while (n % d) == 0:
            if d in memo:
                memo[d]+=1
            else:
                memo[d]=1
            n //= d
        d += 1
    if n > 1:
        if n in memo:
            memo[n]+=1
        else:
            memo[n]=1
primes(m)

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**5*2
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)

ans=1
for x in memo.items():
    ans*=cmb(x[1]+n-1,x[1],mod)
    ans%=mod

print(ans)

Submission status: Accepted

Solution code:
# うまく効率化できなかった
# 2 6=>4 (1,6)*2,(2,3)*2
# 3 12=>18 (1,1,12)*3,(1,2,6)*6,(1,3,4)*6,(2,2,3)*3
# import math
# def comb(a,b):
#     return math.factorial(a)//math.factorial(a-b)//math.factorial(b)
def comb(a,b): # aCb
    b=min(b,a-b)
    result=1
    for i in range(a,a-b,-1):
        result*=i
    for i in range(1,b+1):
        result//=i
    return result

n,m=map(int,input().split())
divisor={}
tmp=m
# for i in range(2,m+1):
#     while tmp%i==0:
#         tmp//=i
#         divisor.setdefault(i,0)
#         divisor[i]+=1
#         if tmp==1:
#             break
i=2
while i*i<=m:
    while tmp%i==0:
        tmp//=i
        divisor.setdefault(i,0)
        divisor[i]+=1
    i+=1
if tmp>1:
    divisor[tmp]=1
# print(divisor)
cnt=1
for key in divisor:
    c=divisor[key]
    cnt*=comb(c+n-1,c)
print(cnt%1000000007)

Submission status: Accepted

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

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

def factorize(n):
    f=[]
    p=2
    cnt=0
    while p**2<=n:
        while n%p==0:
            cnt+=1
            n=n//p
        if cnt!=0:
            f.append([p,cnt])
            cnt=0
        p+=1
    if n!=1:
        f.append([n,1])
    return f

ans=1
mod=10**9+7
f=factorize(m)
for i in range(len(f)):
    k=f[i][1]
    ci=combination(k+n-1,k)%mod
    ans=ans*ci%mod
print(ans)