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:
from collections import Counter


def main():
    """
    1 <= N <= 10^5
    1 <= M <= 10^9

    正整数 N, M
    a1 * a2 * ... * aN = M となる長さNの数列a
    何通りあるか
    数列A1-ai != 数列A2-ai
    """
    N, M = map(int, input().split())

    ans = editorial(N, M)
    print(ans)


def factorize(N):
    """素因数分解

    TODO: もっと速い方法
    素因数がある場合は範囲をsqrtで狭められるが、ない場合愚直に探してしまう
    N以下の素数を見つけて、それだけで対応すれば速いはず
    """
    import math
    factors = []
    while True:
        if N % 2 == 0:
            factors.append(2)
            N //= 2
        else:
            break
    m = int(math.sqrt(N))
    i = 3
    while i <= m:
        add = False
        while True:
            if N % i == 0:
                factors.append(i)
                N //= i
                add = True
            else:
                break
        if add:
            m = int(math.sqrt(N))
        i += 2
    if N > 1:
        factors.append(N)
    return factors


def f(N, M):
    """
    M を素因数分解すると約数とそれらの個数がわかる
    それらの組合せを制約を満たすようにする
    1 * M, M * 1 をわすれないこと:
        1 * 1 * 1 * M もOK

    3 12
        1,1,12: 3P3 / 2!
        2,2,3:  3P3 / 2!
        3,4,1:  3P3
        6,2,1:  3P3

    http://sucrose.hatenablog.com/entry/2014/10/10/235805
    """
    ans = 0
    m = 10 ** 9 + 7
    factors = factorize(M)
    c = Counter(factors)
    print(c)
    return ans


def editorial(N, M):
    """
    https://mathtrain.jp/tyohukuc

    3 12 の例で示せているのに、重複組合せという言葉が頭に浮かばなかった

    解説動画より
    modの世界における逆元?
        重複組合せ
            フェルマーの小定理
            階乗と階乗逆元
        拡張ユークリッド互除法
            今回は出番なし
    """
    def create_tables(N, MOD):
        """
        http://drken1215.hatenablog.com/entry/2018/06/08/210000
        """
        fact_mod = [0] * (N + 1)
        simod = [0] * (N + 1)
        fact_inv_mod = [0] * (N + 1)

        fact_mod[0] = fact_mod[1] = 1
        simod[0] = simod[1] = 1
        fact_inv_mod[0] = fact_inv_mod[1] = 1

        for i in range(2, N + 1):
            fact_mod[i] = (fact_mod[i - 1] * i) % MOD
            simod[i] = MOD - simod[MOD % i] * (MOD // i) % MOD
            fact_inv_mod[i] = (fact_inv_mod[i - 1] * simod[i]) % MOD
            # inv 配列が確実に不要な場面 とは？ (ここでのsimod)
            # inv[n] を逆元計算によって計算しておく
            # finv[i-1] = finv[i] * i % MOD によって finv 配列を後ろから計算していく

        return fact_mod, fact_inv_mod

    def create_fact_mod(N, MOD):
        fact_mod = [0] * (N + 1)
        fact_mod[0] = 1
        fact_mod[1] = 1

        # 階乗のテーブル作成, 累積積によって計算量を落としている
        for i in range(2, N + 1):
            fact_mod[i] = (fact_mod[i - 1] * i) % MOD

        return fact_mod

    def create_seq_inv_mod(N, MOD):
        simod = [0] * (N + 1)
        simod[0] = 1  # 0のままでもよい?
        simod[1] = 1

        # 階乗逆元のテーブル用に作成
        for i in range(2, N + 1):
            simod[i] = (MOD - MOD // i) * simod[MOD % i] % MOD
            # 下記との違いはなにか？
            # simod[i] = MOD - simod[MOD % i] * (MOD // i) % MOD

        return simod

    def create_fact_inv_mod(N, MOD, simod):
        fact_inv_mod = [0] * (N + 1)
        fact_inv_mod[0] = 1
        fact_inv_mod[1] = 1

        # 階乗逆元のテーブル作成
        for i in range(2, N + 1):
            fact_inv_mod[i] = (fact_inv_mod[i - 1] * simod[i]) % MOD

        return fact_inv_mod

    def comb_mod(N, R, fact_mod, fact_inv_mod, MOD):
        """
        組合せ nCr: n! / ((n-r)! * r!)
        上記のmodを逆元を使って表現

        f[n] * f[r] % MOD * f[n-r] % MOD 
        これのために事前にテーブルを作っていた
        """
        return fact_mod[N] * fact_inv_mod[N - R] * fact_inv_mod[R] % MOD

    ans = 1
    m = 10 ** 9 + 7
    factors = factorize(M)
    c = Counter(factors)

    # ref:
    # https://beta.atcoder.jp/contests/abc110/submissions/3253308
    # http://betrue12.hateblo.jp/entry/2018/09/24/020414
    fact_mod = create_fact_mod(N + 100, m)
    simod = create_seq_inv_mod(N + 100, m)
    fact_inv_mod = create_fact_inv_mod(N + 100, m, simod)

    # 重複組合せ: n! / (a! * (b - a)!)
    # 重複組合せ を 各素因数における組合せ結果の掛け合わせで表現
    for i in c.values():
        ans *= comb_mod(N - 1 + i, i, fact_mod, fact_inv_mod, m)
        ans %= m

    return ans


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
mod = 10**9 + 7
n, m = map(int, input().split())
#mの素因数分解
#(prime, power)を要素としてもつ配列を返す関数を作る
def factorize(n):
    fct = []
    b, e = 2, 0
    while b*b <= n:
        while n%b == 0:
            n //= b
            e += 1
        if e > 0:
            fct.append((b, e))
        b += 1
        e = 0
    if n > 1:
        fct.append((n, 1))
    return fct

num = factorize(m)
ans = 1

for p in num:
    for i in range(p[1]):
        ans *= n+i
    for i in range(p[1]):
        ans //= i+1
print(ans%mod)

Submission status: Accepted

Solution code:
# coding: utf-8
n,m=map(int,input().split())
l={}
p=2

while m>=p*p:
    if m%p==0:
        if not p in l.keys():
            l[p]=0
        l[p]+=1
        m//=p
    else:
        p+=1
if not m in l.keys():
    l[m]=0
l[m]+=1

ans=1
for p,q in l.items():
    if p==1:
        continue
    for i in range(q):
        ans*=n+i
    for i in range(q):
        ans//=i+1

print(ans%1000000007)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
MAX_N = 10 ** 5 + 2000
factors, MOD = {}, 10 ** 9 + 7
fact, fact_inv = [1] * (MAX_N+1), [1] * (MAX_N+1)


def prime_factorization(n):
    i = 2
    while i * i <= n:
        while not n % i:
            factors[i] = factors.get(i, 0) + 1
            n //= i
        i += 1

    if n != 1:
        factors[n] = 1


def combination(n, r):
    return fact[n] * fact_inv[r] * fact_inv[n-r] % MOD


def main():
    prime_factorization(M)

    for i in range(1, N+2001):
        fact[i] = fact[i-1] * i % MOD

    fact_inv[N+2000] = pow(fact[N+2000], MOD-2, MOD)
    for i in range(N+1999, -1, -1):
        fact_inv[i] = fact_inv[i+1] * (i+1) % MOD

    ans = 1
    for i, j in factors.items():
        ans = ans * combination(j+N-1, j) % MOD

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
def fact(a,b):
    ans = 1
    while a != b:
        ans *= a
        a -= 1
    return ans
def nCr(n,r):
    return (fact(n,r)) // (math.factorial(n-r))
def nHr(n,r):
    return nCr(n+r-1, r-1)
def prime(n): # nまでの素数を列挙
    import math
    num_list = [i + 1 for i in range(2,n,2)]
    list_prime = [2]
    limit = math.sqrt(n)
    if n == 2:
        return list_prime
    else:
        while True:
            p = num_list[0]
            if p >= limit:
                return list_prime + num_list
            list_prime.append(p)
            num_list = [num for num in num_list if num % p != 0]

def primeFactorization(n):
    import math
    list_prime = prime(int(math.sqrt(n)))
    i = 0
    dict_pF = {}
    dict_primeFactorization = {}
    for pri in list_prime:
        dict_pF[pri] = 0
    while True:
        if n == 1:
            for key, value in dict_pF.items():
                if value != 0:
                    dict_primeFactorization[key] = value
            return dict_primeFactorization
        elif i >= len(list_prime):
            dict_pF[n] = 1
            for key, value in dict_pF.items():
                if value != 0:
                    dict_primeFactorization[key] = value
            return dict_primeFactorization
        p = list_prime[i]
        if n % p == 0:
            n //= p
            dict_pF[p] += 1
            continue
        else:
            i += 1

ans = 1
n,m = map(int, input().split())
if m == 1:
    ans = 1
else:
    for factor,degree in primeFactorization(m).items():
        ans *= (nHr(degree,n)) % (10**9+7)
        
print(ans % (10**9+7))

Submission status: Accepted

Solution code:
import time
import collections
import scipy.misc

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

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

factors = collections.Counter(prime_decomposition(M))
t_elps = time.time()
#print(f"{t_elps - t_strt} [sec]")
num_pattern = 1;

for exponent in factors.values():
    tmp_num_pattern = scipy.misc.comb(exponent + N -1, N-1, exact = True) 
    num_pattern = num_pattern * int(tmp_num_pattern)
    
print(num_pattern%(10**9+7))

Submission status: Accepted

Solution code:
import math

# import time


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)


n, m = map(int, input().split())
# start = time.time()
primes = get_primes(m)
elems = []
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
# print(primes)

# print(time.time() - start)
ans = 1
for i in divides.values():
    ans *= combination(i + n - 1, i)
print(ans % (1000000007))
# print(time.time() - start)

Submission status: Accepted

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

import math
class PrimeUtils:
    @staticmethod
    def primes_sieve(n):
        sieve = [True] * (n + 1)
        for i in range(2, n + 1):
            if sieve[i]:
                for j in range(i + i, n + 1, i):
                    sieve[j] = False
        return [i for i, x in enumerate(sieve[2:], 2) if x]
    @staticmethod
    # Prime Factor Decomposition
    def pfd(n):
        rn = math.ceil(math.sqrt(n))
        primes = PrimeUtils.primes_sieve(rn)

        factors = []
        cur = n
        for p in primes:
            cnt = 0
            while True:
                div, rem = divmod(cur, p)
                if rem == 0:
                    cnt += 1
                    cur = div
                else:
                    break
            if cnt != 0:
                factors.append((p, cnt))
        if cur != 1 or n == 1:
            factors.append((cur, 1))
        return factors

import itertools, operator, math
class Combination:
    def __init__(self, fact=math.factorial, div=operator.itruediv):
        self.fact = fact
        self.div = div
    def C(self, n, m):
        if n < m: return 0
        if m == 0 or n == m: return 1
        return self.div(
                self.fact(n),
                self.fact(n - m) * self.fact(m)
            )
    def H(self, n, r):
        return self.C(n - 1 + r, r)

class GFp:
    def __init__(self, p):
        self.p = p
    def inv(self, v):
        return pow(v, self.p - 2, self.p)

class CachedFactorial:
    def __init__(self, n, mod):
        self.mod = mod
        self.fact_cache = list(
                itertools.accumulate(
                        itertools.chain(
                                [1],
                                range(1, n+1)
                        ),
                        lambda a,x: (a * x) % mod
                )
        )
    def factorial(self, n):
        return self.fact_cache[n]

class CachedComb(Combination):
    def __init__(self, n, mod):
        self.mod = mod
        self.gfp = GFp(mod)

        self.n = n
        self.fact = CachedFactorial(n, mod)
        super().__init__(
             self.fact.factorial,
             lambda x, y: (x * self.gfp.inv(y)) % self.mod
        )

ps = PrimeUtils.pfd(M)
cc = CachedComb(N + max(x[1] for x in ps), mod)
ans = 1
for p, c in ps:
    if p == 1: continue
    cmb = cc.H(N, c)
    ans = ans * cmb % mod
print(ans)

Submission status: Accepted

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


import array
import collections
import functools
import itertools
import math
import random


M = 10 ** 9 + 7


def sieve_of_eratosthenes(end, typecode="L"):
    """Enumerates the prime numbers below the given integer.
    :param int end: Prime numbers below this integer will be enumerated.
    :param str typecode: The type of the array to be returned (optional).
    :return: The array of the prime numbers.
    :rtype: :class:`array.array`
    """

    assert end > 1
    is_prime = array.array("B", (True for i in range(end)))
    is_prime[0] = False
    is_prime[1] = False
    primes = array.array(typecode)
    for i in range(2, end):
        if is_prime[i]:
            primes.append(i)
            for j in range(2 * i, end, i):
                is_prime[j] = False
    return primes


def factorize_trial_division(n, typecode="L"):
    """Factorizes the given integer in prime numbers by trial division.
    :param int n: The integer to be factorized.
    :param str typecode: The type of the array to be returned (optional).
    :return: The array of factors.
    :rtype: :class:`array.array`
    """
    factors = array.array(typecode)
    if n < 2:
        return factors
    for p in sieve_of_eratosthenes(math.ceil(math.sqrt(n)) + 1):
        if p * p > n:
            break
        while n % p == 0:
            factors.append(p)
            n //= p
    if n > 1:
        factors.append(n)
    return factors


def is_prime_miller_rabin(n, k=50):
    """Determing whether the given integer is prime by the Miller-Rabin test.
    :param int n: The integer to be checked.
    :param int k: The parameter representing the accuracy of the determination.
    :return: Whether n is prime or not.
    :rtype: bool
    """
    assert n > 0
    if n == 2:
        return True
    elif n == 1 or n % 2 == 0:
        return False
    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1
    for _ in range(k):
        a = random.randint(1, n - 1)
        if pow(a, d, n) != 1:
            for r in range(0, s):
                if pow(a, d * 2 ** r, n) == n - 1:
                    break
            else:
                return False
    return True


class ModPrime(object):

    def __init__(self, max_n=500000, mod=M):
        # cf. http://hos.ac/slides/20130319_enumeration.pdf
        self.max_n = max_n
        assert is_prime_miller_rabin(mod)
        self.mod = mod
        self.invs = [None, 1]
        for i in range(2, self.max_n + 1):
            self.invs.append(mod - mod // i * self.invs[mod % i] % mod)
        self.facts = [1]
        self.fact_invs = [1]
        for i in range(1, self.max_n + 1):
            self.facts.append(self.facts[i - 1] * i % mod)
            self.fact_invs.append(self.fact_invs[i - 1] * self.invs[i] % mod)
    
    def inv(self, n):
        return self.invs[n]
    
    def fact(self, n):
        return self.facts[n]
    
    def fact_inv(self, n):
        return self.fact_invs[n]
    
    def comb(self, n, r):
        if r < 0 or r > n:
            return 0
        return self.fact(n) * self.fact_inv(r) % self.mod * self.fact_inv(n - r) % self.mod
    
    def multi_choose(self, n, r):
        return self.comb(n + r - 1, r)


def mod_prod(ys, mod=M):
    xs = itertools.chain((1, ), ys)
    return functools.reduce(lambda x, y: x * y % mod, xs) % mod


def solve(n, m, mod=M):
    fs = collections.Counter(factorize_trial_division(m))
    mp = ModPrime(mod=M)
    res = mod_prod((mp.multi_choose(n, v) for v in fs.values()), mod=M)
    return res


def main():
    n, m = (int(z) for z in input().split())
    res = solve(n, m)
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
ex = []
i = 2
while i**2 <= M:
    j = 0
    while M % i == 0:
        M //= i
        j += 1
    if j != 0:
        ex.append(j)
    i += 1
if M > 1: # M is a prime.
    ex.append(1)

mod = 10**9+7
ans = 1
for e in ex: # (e+N-1) choose e
    temp = 1
    for i in range(e):
        temp *= (e+N-1 - i)
    for i in range(e):
        temp //= (e - i)
    ans *= temp
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
M = 10 ** 9 + 7

def main():
    n, m = [int(s) for s in input().split()]

    print(solve(m, n, 10 ** 9 + 7))

def solve(m, n, mod):
    r = 1

    for _, c in get_prime_factors(m):
        r = r * mod_comb(c + n - 1, c, mod) % mod
    return r

def mod_comb(n, k, m):
    r = 1
    for i in range(1, k + 1):
        r = r * (n - k + i) * mod_inv(i, m) % m
    return r

def mod_inv(n, m):
    r0, r1 = n, m
    x, y, u, v = 1, 0, 0, 1

    while r1:
        k, r0, r1 = r0 // r1, r1, r0 % r1
        x, y, u, v = u, v, x - k * u, y - k * v

    if r0 != 1:
        raise ValueError

    return x

def get_prime_factors(n):
    from itertools import count, takewhile
    r = n

    for i in takewhile(lambda x: x * x <= r, count(2)):
        c = 0
        while r % i == 0:
            c += 1
            r //= i
        yield i, c

    if r != 1:
        yield r, 1

main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
i=2
s=[]
while i*i<=m:
  j=0
  while m % i == 0:
    m//=i
    j+=1 
  if j:
    s+=[j]
  i+=1
a=1
if m > 1:
  s+=[1]
  
for v in s:
  c = 1
  for i in range(v):
    c = c * (n+i) // (1+i)
  a = a * c % (10**9+7)
print(a)

Submission status: Accepted

Solution code:
import sys

MOD = 10 ** 9 + 7

def main():
    n, m = [int(s) for s in input().split()]
    print(solve(m, n))

def solve(m, n):
    factors = list(get_prime_factors(m))
    h = max((c for f, c in factors), default=0)

    table = dict()
    table[1] = [1 for _ in range(h + 1)]

    i = 1
    while i < n:
        j = n & (i - 1)
        table[i * 2] = [0 for _ in range(h + 1)]
        if n & i != 0 and j != 0:
            table[i + j] = [0 for _ in range(h + 1)]
        for x in range(h + 1):
            for y in range(h + 1 - x):
                table[i * 2][x + y] = (table[i * 2][x + y] + table[i][x] * table[i][y]) % MOD
                if n & i != 0 and j != 0:
                    table[i + j][x + y] = (table[i + j][x + y] + table[i][x] * table[j][y]) % MOD

        if n & i == 0:
            del table[i]
        if n & i != 0 and j != 0:
            del table[i]
            del table[j]

        i *= 2

    ans = 1
    for f, c in factors:
        ans = ans * table[n][c] % MOD
    return ans

def get_prime_factors(n):
    import itertools

    m = n
    for i in itertools.count(2):
        if i * i > m:
            break

        c = 0
        while True:
            x, y = divmod(m, i)
            if y != 0:
                break
            c += 1
            m = x
        if c != 0:
            yield i, c

    if m != 1:
        yield m, 1


main()

Submission status: Accepted

Solution code:
from math import factorial
MOD = 10**9 + 7

def prime_factor(n):
    res = []
    d = 2
    while d * d <= n:
        if n % d == 0:
            cnt = 0
            while n % d == 0:
                cnt += 1
                n //= d
            res.append(cnt)
        d += 1
    if n > 1:
        res.append(1)
    return res

N, M = map(int, input().split())
ans = 1
for c in prime_factor(M):
    for i in range(c):
        ans *= N + i
    ans //= factorial(c)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

def mod_pow(a, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return mod_pow(a, p // 2) ** 2 % MOD
    else:
        return a * mod_pow(a, p - 1) % MOD

def calc_comb(a, b):
    if b > a - b:
        return calc_comb(a, a - b)
    ans_mul, ans_div = 1, 1
    for i in range(b):
        ans_mul *= a - i
        ans_div *= i + 1
        ans_mul %= MOD
        ans_div %= MOD
    return ans_mul * mod_pow(ans_div, MOD - 2) % MOD

def main():
    N, M = map(int, input().split())
    i = 2
    ans = 1
    while i * i <= M:
        if M % i == 0:
            cnt = 0
            while M % i == 0:
                cnt += 1
                M //= i
            ans *= calc_comb(N + cnt - 1, N - 1)
            ans %= MOD
        i += 1
    if M > 1:
        ans *= calc_comb(N + 1 - 1, N - 1)
        ans %= MOD
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
n,m = map(int,input().split())
mm = int(math.sqrt(m))
s = {}
for i in range(2,mm+2):
    if m%i != 0:
        continue
    while m%i == 0:
        m = m//i
        s[i] = s.get(i, 0) + 1
    if m == 1:
        break
if m>=2:
    s[1] = 1
ans = 1
mod = 10**9+7
for i in s.values():
    for j in range(1,i+1):
        ans = ans * (n+j-1)//(j)
    ans %=mod
print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

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)
    
MOD = 10**9+7

n,m = li()

# 二項係数の準備
inv = inv_mod(n+100,MOD)
fac = fact(n+100,MOD)
fac_inv = fact_inv(n+100,inv,MOD)

primes = factorize(m)
ans = 1
for p in primes.values():
    ans = ans * nHr(n,p,MOD,fac,fac_inv) % MOD
    
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin


def num_of_prime_factorization(n):
    i = 2
    table = []
    while i * i <= n:
        loop_num = 0
        while n % i == 0:
            n //= i
            loop_num += 1
            if n % i != 0:
                table.append(loop_num)
        i += 1
    if n > 1:
        table.append(1)
    return table


def comb(n, r):
    a = 1
    for num in range(n, n - r, -1):
        a *= num

    b = 1
    for num in range(r, 0, -1):
        b *= num

    return a // b


N, M = [int(i) for i in stdin.readline().rstrip().split()]

lst = num_of_prime_factorization(M)
ans = 1

for b in lst:
    ans *= comb(b + N - 1, b)

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

Submission status: Accepted

Solution code:

iN,iM = [int(x) for x in input().split()]
iD = 10**9 +7 #法

def fPrimeCounter(iM):
    iS = int(iM ** 0.5) + 1
    aRet = []
    for i in range(2,iS + 1):
        iCounter = 0
        while iM % i == 0:
            iM /= i
            iCounter += 1
        if 0 < iCounter : aRet.append(iCounter)
        if iM == 1 : break
    if 1 < iM  : aRet.append(1)
    return aRet
def fnCr(iN,iR,iD):
    iR = min(iR,iN-iR)
    if iR == 0 :
        return 1
    elif iR == 1 :
        return iN
    return (iN % iD) * pow(iR,iD-2,iD) * fnCr(iN-1,iR-1,iD) % iD

aP = fPrimeCounter(iM)
#if aP == []:
#   print(1)
#   exit()
iRet = 1
for i in aP:
    # i + iN -1  C  iN -1
    iRet *= fnCr(i+iN-1,i,iD)
iRet %= iD
print(iRet)

Submission status: Accepted

Solution code:
from collections import Counter

from scipy.misc import comb

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

mod = 10**9 + 7


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


p = prime_decomposition(M)
p = Counter(p)

ans = 1
for pi in p.values():
    res = comb(pi + N - 1, N - 1, exact=True)
    ans = (ans * res) % mod
print(ans)

Submission status: Accepted

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

MOD = 10 ** 9 + 7

if m == 1:
    print('1')
    exit()

factor = []
temp = 0
x = 2
while m > 1:
    if m % x == 0:
        m //= x
        temp += 1
    elif temp > 0:
        factor.append(temp)
        temp = 0
        x += 1
    else:
        x += 1
factor.append(temp)

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

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

    nCr[(n, r)] = result
    return result;

ans = 1
for x in factor:
    ans *= cmb(x + n - 1, n - 1)
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:

iN,iM = [int(x) for x in input().split()]
iD = 10**9 +7 #法

def fPrimeCounter(iM):
    iS = int(iM ** 0.5) + 1
    aRet = []
    for i in range(2,iS + 1):
        iCounter = 0
        while iM % i == 0:
            iM = iM / i
            iCounter += 1
        if 0 < iCounter : aRet.append(iCounter)
        if iM == 1 : break
    if 1 < iM  : aRet.append(1)
    return aRet

#二分累乗法 iDを法として
def fBiPow(iX,iN,iD):
    iY = 1
    while iN > 0:
        if iN % 2 == 0:
            iX = iX * iX % iD
            iN = iN // 2
        else:
            iY = iX * iY % iD
            iN = iN - 1
    return iY

aP = fPrimeCounter(iM)
if len(aP) == 0:
    print(1)
    exit()
iMax = max(aP) + iN - 1
aM = [1] * (iMax + 1)
#階乗 iD を法とした
for i in range(1,iMax + 1):
    aM[i] = aM[i-1] * i  % iD
aInvM = [1]* (iMax + 1)
aInvM[iMax] = fBiPow(aM[iMax],iD-2,iD)
#階乗の逆元 iD を法とした
for i in range(iMax,0,-1):
    aInvM[i-1] = aInvM[i]*i % iD

iRet = 1
for i in aP:
    # i + iN -1  C  iN -1
    iRet *= aM[i+iN-1] * aInvM[iN-1] * aInvM[i] % iD
iRet %= iD
print(iRet)

Submission status: Accepted

Solution code:
import copy

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

#x以下の素数の列挙   
import math
x=math.floor(math.sqrt(10**9))
L=math.floor(math.sqrt(x))#平方根を求める
Primelist=[i for i in range(x+1)]
Primelist[1]=0#素数でないものは0にする.
for i in Primelist:
    if i>L:
        break
    if i==0:
        continue
    for j in range(2*i,x+1,i):
        Primelist[j]=0
Primes=[Primelist[j] for j in range(x+1) if Primelist[j]!=0]

def fact(M):#約数の列挙
    if M==1:
        return {1}
    
    DICT=dict()#素因数分解
    i=0
    while M!=1 and i<len(Primes):
        if M%Primes[i]==0:
            DICT[Primes[i]]=DICT.get(Primes[i],0)+1
            M=M//Primes[i]
        else:
            i+=1

    if M!=1:
        DICT[M]=1

    VALUES=list(DICT.values())
    KEYS=list(DICT.keys())

    LIST=[1]

    for i in range(len(DICT)):
        NOWLIST=copy.copy(LIST)
        for l in NOWLIST:
            for j in range(0,VALUES[i]+1):
                LIST.append(l*KEYS[i]**j)

    return set(LIST)

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)%mod*pow(min(b,a-b)-i,mod-2,mod)%mod

    return ANS%mod



SET=fact(M)
factor=dict()

for j in SET:
    factor[j]=fact(j)

DP=dict()
defaultans=[0 for i in range(40)]
defaultans[1]=1
defaultans=tuple(defaultans)

def dp(m):
    ANS=[0 for i in range(40)]
    if m==1:
        return defaultans
    
    for j in factor[m]:
        #print(j,factor[m])

        if j==1:
            continue
        else:
            if DP.get(m//j,-1)!=-1:
                NEXT=DP[m//j]
            else:
                NEXT=dp(m//j)

            for k in range(39):
                ANS[k+1]=(ANS[k+1]+NEXT[k])%mod

            #print(m//j,ANS,NEXT)

        DP[m]=ANS
    return ANS
            
LIST=dp(M)
ANS=0
for i in range(40):
    if LIST[i]!=0:
        ANS=ANS+Combi2(N,i-1)*LIST[i]%mod

print(ANS%mod)

Submission status: Accepted

Solution code:
import math


def modinv(a, b, m):
    # a / b (mod m) を求める。
    # 例えば、 9 / 4 (mod 13) = 12となる。
    # まず、 1 / b (mod m) を求める。
    for i in range(m):
        if (i * m + 1) % b == 0:
            tmp = int((i * m + 1) / b)
            break

    # a / b (mod m) は、 1 / b (mod m) に a を掛けて余りを取れば求められる。
    return (tmp * a) % m


def factoring(n):
    pf = {}
    num = n

    if n == 1:
        return {}

    while True:
        flag = 0

        for i in range(2, math.floor(math.sqrt(n)) + 1):
            if num % i == 0:
                num = num / i
                flag = 1
                if i in pf:
                    pf[i] += 1
                else:
                    pf[i] = 1

                if num == 1.0:
                    return pf
                else:
                    break

        if flag == 0:
            if num in pf:
                pf[num] += 1
            else:
                pf[num] = 1
            return pf


N, M = map(int, input().split())
# 仕切りの数: N - 1 個
# 素数の約数p1の数: n1 個
# p2の数: n2個
# ... の重複組合せの個数を求める。
MOD = 10 ** 9 + 7

# まず、素因数分解を行う。
pf = factoring(M)

ans = 1
for key in pf:
    for i in range(pf[key]):
        ans = ans * (N - 1 + pf[key] - i) % MOD
    for i in range(2, pf[key] + 1):
        ans = modinv(ans, i, MOD)

print(ans)

Submission status: Accepted

Solution code:
from math import log2
N, M = map(int, input().split())

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 #出力の制限
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

#print(log2(10**9)) -> 29.8 < 30 = vmaxとみなせる
for i in range( 2, N + 1 + 30 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

Divs = {}

i = 2
while i * i <= M:
  first_time = True
  while M % i == 0:
    if first_time:
      Divs[i] = 1
      first_time = False
    else:
      Divs[i] = Divs[i] + 1
    M = M // i
  i += 1

if M > 1:
  Divs[M] = 1

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


print(ans)
#print(Divs)