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 sys

MOD = 10 ** 9 + 7
# MOD = 998244353
def make_tables(n=10 ** 9, r=2 * 10 ** 6, p=MOD):
  fac = [None] * (r + 1); fac[0] = 1
  for i in range(r): fac[i+1] = fac[i] * (i + 1) % p
  ifac = [None] * (r + 1); ifac[r] = pow(fac[r], p - 2, p)
  for i in range(r, 0, -1): ifac[i-1] = ifac[i] * i % p
  n_choose = [None] * (r + 1); n_choose[0] = 1
  for i in range(r): n_choose[i+1] = n_choose[i] * (n - i) % p
  for i in range(r + 1): n_choose[i] = n_choose[i] * ifac[i] % p
  return fac, ifac, n_choose

fac, ifac, n_choose = make_tables()

def mod_choose(n, r, p=MOD):
  if r > n or r < 0: return 0
  return fac[n] * ifac[r] % p * ifac[n-r] % p

def nHr(n, r, p=MOD):
  return fac[n-1+r] * ifac[n-1] % p * ifac[r] % p

def sieve_of_eratosthenes(n=10 ** 6):
  sieve = [1] * (n + 1); sieve[0] = sieve[1] = 0
  for i in range(2, int(n ** 0.5) + 1):
    if not sieve[i]: continue
    for j in range(i * 2, n + 1, i): sieve[j] = 0
  prime_numbers = [i for i in range(2, n + 1) if sieve[i]]
  return sieve, prime_numbers

is_prime, prime_numbers = sieve_of_eratosthenes()

def prime_factorize(n):
  res = dict()
  if n < 2: return res
  border = int(n ** 0.5)
  for p in prime_numbers:
    if p > border: break
    while n % p == 0: res[p] = res.get(p, 0) + 1; n //= p
    if n == 1: return res
  res[n] = 1
  return res

def prime_factorize_factorial(n):
  res = dict()
  for i in range(2, n + 1):
    for p, c in prime_factorize(i).items(): res[p] = res.get(p, 0) + c
  return res

n, m = map(int, sys.stdin.readline().split())

def main():
  res = 1
  for p, c in prime_factorize(m).items():
    res *= nHr(n, c)
    res %= MOD 
  print(res)

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

#素因数分解
def prime_factorize(n):
    a = []
    a.append(1)
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    
    b = [[],[]]
    cnt = 1
    for i in range(len(a)+1):
        if i > 0 and i < len(a):
            if a[i] == a[i-1]:
                cnt += 1
            else:
                b[0].append(a[i-1])
                b[1].append(cnt)
                cnt = 1
        if i == len(a) and i > 0:
            b[0].append(a[i-1])
            b[1].append(cnt)
        elif i == len(a) and i == 0:
            b[0].append(a[i])
            b[1].append(cnt)
    return b

#コンビネーション(特殊例)
def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

N = 10**5 + 100
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

n, m = MAP()
mar = prime_factorize(m)
arr = mar[1]
ans = 1
for i in range(1, len(arr)):
    ans *= cmb(arr[i] + n - 1, arr[i])
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

class Combination:
    def __init__(self, size):
        self.size = size + 2
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % MOD
            self.inv[i] = -self.inv[MOD % i] * (MOD // i) % MOD
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % MOD

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % MOD

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % MOD) % MOD

    def nhr(self, n, r):  # 重複組合せ: x_1 + ... + x_n = r
        return self.ncr(n + r - 1, n - 1)

N, M = map(int, input().split())
comb = Combination(N + 100)

def primeCount(N):
    R = int(N**(0.5)) + 1  # 素数の範囲
    primes = {}  # 素数のリスト
    n = N
    for num in range(2, R):
        primes[num] = 0
        while n % num == 0:
            n //= num
            primes[num] += 1
    if n > 1 :
        primes[n] = 1
    return { key : val for key, val in primes.items() if val > 0}  # フィルターをかける

ans = 1
for c in primeCount(M).values():
    ans *= comb.nhr(N, c)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

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

def factoring(k): #kを因数分解し、素因数とその個数を辞書に入れて返す。
    import math
    dic = dict()
    n = int(math.sqrt(k))+2
    for i in range(2, n):
        count = 0
        while k%i == 0:
            count += 1
            k = k//i
        if count != 0:
            dic[i] = count
    if k != 1: #sqrt(k)までチェックしてもkが1になっていない --> kが素因数
        dic[k] = 1
    return dic

class Factorial:
    def __init__(self, n, mod):
        self.f = [1]
        self.mod = mod
        for j in range(1, n + 1):
            self.f.append(self.f[-1] * j % mod)
        self.i = [pow(self.f[-1], mod - 2, mod)]
        for j in range(n, 0, -1):
            self.i.append(self.i[-1] * j % mod)
        self.i.reverse()
    def factorial(self, j):
        return self.f[j]
    def ifactorial(self, j):
        return self.i[j]
    def comb(self, n, k):
        return self.f[n] * self.i[n - k] % self.mod * self.i[k] % self.mod if n >= k else 0




C = Factorial(N + 100, MOD).comb

ans = 1
dic = factoring(M)
for tmp in dic:
    # print (tmp, dic[tmp])
    ans *= C(dic[tmp] + N - 1, dic[tmp])
    ans %= MOD

print (ans)

Submission status: Accepted

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

MOD = 10**9+7

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

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

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

    def permutation(self, n, r):
        if r == 0: return 1
        return self.fac[n] * self.pow(self.fac[n-r], MOD-2) % MOD

from collections import *
import sys
def get_prime(n):
    c = Counter()

    while not n % 2:
        c[2] += 1
        n //= 2
    i = 3

    while i**2 <= n:
        while not n % i:
            c[i] += 1
            n //= i
        i += 2

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

    return c

prime = get_prime(M)
if not prime: print(1); sys.exit()

comb = Comb(N+max([m for m in prime.values()]))

ans = 1

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

Submission status: Accepted

Solution code:
from collections import defaultdict
def factorization(n):
    arr = {}
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr[i] = cnt

    if temp != 1:
        arr[temp] = 1
    if len(arr.keys()) == 0:
        arr[n] = 1
    return arr


def prepare(n, MOD):

    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return factorials, invs

import math
from itertools import combinations
from collections import Counter
MOD = 1000000007

def solve():
    N, M = map(int, input().split())
    temp = factorization(M)
    #print(temp)
    max_num = max(temp.values())
    factorials, invs = prepare(N+max_num-1, MOD)
    #print(factorials, invs)
    ans = 1
    for i, j in temp.items():
        if i == 1:
            break
        ans *= factorials[N+j-1]
        ans %= MOD
        ans *= invs[N-1]
        ans %= MOD
        ans *= invs[j]
        ans %= MOD
        #print(ans)
    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
def factorization(n):
    arr = dict()
    temp = n
    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr[i] = cnt

    if temp != 1:
        arr[temp] = 1

    if not arr and n != 1:
        arr[n] = 1

    return arr


MOD = 10 ** 9 + 7
MAX = 10 ** 5 + 50
modinv = lambda a, mod=10 ** 9 + 7: pow(a, mod - 2, mod)
fac, inv = [1] * MAX, [1] * MAX
for i in range(1, MAX):
    fac[i] = fac[i - 1] * i % MOD
    inv[i] = modinv(fac[i])
comb = lambda n, k: fac[n] * inv[k] * inv[n - k] % MOD

N, M = map(int, input().split())
ans = 1
for v in factorization(M).values():
    ans = (ans * comb(N + v - 1, v) % MOD)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from functools import reduce
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
def pow_k(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K = (K * x)
        x = (x * x)
        n //= 2
    return (K * x)
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0
def modinv(a, m):
    g, x, y = xgcd(a, m)
    return x % m
def modmul(a,b):
    return a * b % 1000000007
def comb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(modmul, range(n, n - r, -1))
    under = reduce(modmul, range(1,r + 1))
    return over * modinv(under, 1000000007)

N,M = (int(x) for x in input().split())
ans = 1
if M == 1:
    print('1')
else:
    a = Counter(prime_factorize(M))
    for x in a.values():
        ans = ans * comb(N+x-1,x) % 1000000007
    print(ans)

Submission status: Accepted

Solution code:
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append(cnt)

    if temp!=1:
        arr.append(1)

    return arr

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

P, Q = map(int,input().split())
L = factorization(Q)
ans = 1
for i in L:
    ans *= cmb(P-1+i,i,mod)

print(ans % mod)

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
from sys import exit
import math
n, m = map(int, input().split())
dic = dd(int)

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

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

for i in range(2, math.ceil(m**0.5) + 3):
    while m % i == 0:
        m //= i
        dic[i] += 1
if m != 1:
    dic[m] = 1
#print(dic)

ans = 1
mod = 10**9 + 7
for count in dic.values():
    ans *= combinations_count(count + n - 1, n-1) % mod

print(ans % mod)

Submission status: Accepted

Solution code:
def modpow(a,n):
  if n<1:
    return 1
  ans=modpow(a,n//2)
  ans=(ans*ans)%mod
  if n%2==1:
    ans*=a
  return ans%mod

def conb(n,i):
  inv,ans=1,1
  for j in range(1,i+1):
    ans=ans*(n-j+1)%mod
    inv=inv*j%mod
  return (ans*modpow(inv,mod-2))%mod


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append(cnt)
    if temp!=1:
        arr.append(1)

    if arr==[]:
        arr.append(1)
    return arr



mod=10**9+7
N,M=[int(x) for x in input().rstrip().split()]
fact=factorization(M)
ans=1

if M==1:
  print(1)
else:
  for i in fact:
    ans*=conb(i+N-1,N-1)
  print(ans%mod)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    n, m = map(int, input().split())
    # https://atcoder.jp/contests/abc156/submissions/11621672
    def modpow(a, b, mod=10 ** 9 + 7):
        ret = 1
        while b > 0:
            if b % 2 == 1:
                ret = ret * a % mod
            a = a * a % mod
            b //= 2
        return ret


    def modcomb(n, c, mod=10 ** 9 + 7):
        if n<c:
            return 0
        if c > n - c:
            c = n - c
        u, d = 1, 1
        for i in range(c):
            u = u * (n - i) % mod
            d = d * (i + 1) % mod
        return u * modpow(d, mod - 2) % mod


    """mod = 10 ** 9 + 7
    n, a, b = map(int, input().split())
    ans = (modpow(2, n) - 1) % mod
    ans = (ans-modcomb(n, a)) % mod
    ans = (ans-modcomb(n, b)) % mod
    print(ans)"""

    # combどうしの積をとると余りがずれるので避ける！　普通のcombを計算して最後にmodをとって。

    import math

    # cf. https://qiita.com/suecharo/items/14137fb74c26e2388f1f
    def make_prime_list_2(num):
        if num < 2:
            return []

        # 0のものは素数じゃないとする
        prime_list = [i for i in range(num + 1)]
        prime_list[1] = 0  # 1は素数ではない
        num_sqrt = math.sqrt(num)

        for prime in prime_list:
            if prime == 0:
                continue
            if prime > num_sqrt:
                break

            for non_prime in range(2 * prime, num, prime):
                prime_list[non_prime] = 0

        return [prime for prime in prime_list if prime != 0]

    def prime_factorization_2(num):
        """numの素因数分解
        素因数をkeyに乗数をvalueに格納した辞書型dict_counterを返す"""

        if num == 1:
            return False
        else:
            num_sqrt = math.floor(math.sqrt(num))
            prime_list = make_prime_list_2(num_sqrt)

            dict_counter = {}  # 何度もこの関数を呼び出して辞書を更新したい時はこれを引数にして
            # cf. https://atcoder.jp/contests/arc034/submissions/12251452

            for prime in prime_list:
                while num % prime == 0:
                    if prime in dict_counter:
                        dict_counter[prime] += 1
                    else:
                        dict_counter[prime] = 1
                    num //= prime
            if num != 1:
                if num in dict_counter:
                    dict_counter[num] += 1
                else:
                    dict_counter[num] = 1

            return dict_counter

    ans = 1
    if not prime_factorization_2(m):
        print(1)
    else:
        d = prime_factorization_2(m)
        mod = 10 ** 9 + 7

        for k, v in d.items():
            ans = ans * modcomb(v + n - 1, n - 1)
        print(ans % mod)


resolve()

Submission status: Accepted

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


MOD = 1000000007  # type: int


def factor(n: int):
    i = 2
    cnt = 0
    while n % i == 0:
        n //= i
        cnt += 1
    if cnt > 0:
        yield i, cnt

    i = 3
    while i * i <= n:
        cnt = 0
        while n % i == 0:
            n //= i
            cnt += 1
        if cnt > 0:
            yield i, cnt
        i += 2

    if n > 1:
        yield n, 1


def comb(n: int, r: int):
    if n - r < r:
        return comb(n, n - r)
    ans = 1
    for i in range(r):
        ans *= n - i
    for i in range(r):
        ans //= i + 1
    return ans


def solve(N: int, M: int):
    ans = 1
    for _p, cnt in factor(M):
        ans *= comb(N - 1 + cnt, cnt) % MOD
        ans %= MOD
    print(ans)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    solve(N, M)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
from collections import defaultdict
N, M = list(map(int, input().split(' ')))
if M == 1:
    print(1)  # a_i = 1 for all i
    exit(0)
# prime factorization of M
fact = defaultdict(int)
for i in range(2, int(math.sqrt(M) + 1)):
    while M % i == 0:
        M //= i
        fact[i] += 1
if M != 1:
    # M is prime
    fact[M] = 1
# calculate answer
answer = 1
mod = 10**9 + 7
for f in fact.values():
    # calc combination(f + N - 1, f) = (f + N - 1) * ... * N / f!
    numerator = 1
    denominator = 1
    for i in range(f):
        numerator *= (N + i)
        denominator *= (i + 1)
    answer *= (numerator // denominator)
    answer %= mod
print(answer)

Submission status: Accepted

Solution code:
'''h2d5
ポイントは重複組み合わせ（仕切りと中身）と素因数因数分解
N+素因数分解の指数-1から指数を選ぶ組み合わせ（指数-1が仕切りの枚数）
nPr=n!/(n-r)!   
nCr=n!/(n-r)!*r!=(n*(n-1)*...*(n-r+1))/r!(分子分母は共にｒ個)
'''
import math
MOD=10**9+7

def comb(n,r):
  nPr=1
  fact_r=1
  for i in range(r):
    nPr*=n-i
    fact_r*=r-i
  return nPr//fact_r

N,M=map(int,input().split())
fact={}
for i in range(2,int(math.sqrt(M))+1):
  if M==1:
    break
  while(M%i==0):#エラトステネスの篩
    M//=i
    if not i in fact:#素因数がなければ追加
      fact[i]=1
    else:#素因数があれば増加
      fact[i]+=1  
if M!=1:#素数のケース
  fact[M]=1
  
answer=1
for r in fact.values():
  answer*=comb(N+r-1,r)#重複組み合わせ
  answer%=MOD
  
print(answer)

Submission status: Accepted

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

mod = 10 ** 9 + 7
N = 200000

#逆元テーブル
inv_t = [0]+[1]
for i in range(2, N):
  inv_t += [inv_t[mod % i] * (mod - int(mod / i)) % mod]

#階乗計算
kai = [1, 1]
rev_kai = [1, inv_t[1]]
for i in range(2, N):
	kai.append(kai[-1] * i % mod)
	rev_kai.append(rev_kai[-1] * inv_t[i] % mod)

# コンビネーション計算
def cmb(n, r):
	return kai[n] * rev_kai[r] * rev_kai[n-r] % mod

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

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

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

    return arr

ans = 1

for _, cnt in factorization(m):
    if _ == 1:
        break
    ans = ans * cmb(cnt + n - 1, n - 1) % mod

print(ans)

Submission status: Accepted

Solution code:
MOD=10**9+7
def factorization(n):
    arr=[]
    tmp=n
    for i in range(2,int(n**0.5)+1):
        if(tmp%i==0):
            cnt=0
            while tmp%i==0:
                cnt+=1
                tmp//=i
            arr.append([i,cnt])
    if(tmp!=1):
        arr.append([tmp,1])
    return arr
def com(n,k,mod):
    res=1
    tmp=1
    for i in range(1,k+1):
        res=res*(n-i+1)%mod
        tmp=tmp*i%mod
    a=pow(tmp,mod-2,mod)
    return res*a%mod
N,M=map(int,input().split())
a=1
arr=factorization(M)
for x,y in arr:
    a=(a*com(y+N-1,N-1,MOD))%MOD
print(a)

Submission status: Accepted

Solution code:
"""
---アルゴリズム概要---
Mを構成する素因数を、a1~aNの各スロットにいくつ置くのか、を考える問題。
まずは試し割りによってMを素因数分解。
重複組合せの公式で各素因数の配置パターンを算出し累乗していく。

試し割りは、O(√M)の計算量で処理できる。
√Mを超える素因数は、多くても一つしか存在しないため、√Mを超える値で試し割りをする必要はない。
もし√Mまでの値で試し割りを終えた段階で、Mを素因数分解しきれていなければ、残った商こそが√Mを超える唯一の素因数である。

簡単に証明
もし√Mを超える素因数が２つ存在しているとしよう。
それらは、(√M + α)と(√M + β)というふうに表すことができる。
この２つの積は明らかにMの値を超えてしまう。つまり前提に矛盾する。
したがって、√Mを超える素因数は多くても一つ
"""
from collections import Counter
import math

N,M = map(int,input().split())
factors = []

while M%2 == 0:
    M//=2
    factors.append(2)
    
f = 3
while f**2 <= M:
    while M%f==0:
        M//=f
        factors.append(f)
    f+=2
if M!=1:
    factors.append(M)

factors = Counter(factors)

ans = 1
for k in factors.values():
    ans *= math.factorial(k+N-1)//(math.factorial(N-1)*math.factorial(k))

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

Submission status: Accepted

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

def main():
    N,M = map(int,input().split())
    MOD = 10**9+7
    
    def factorization(n):
        arr = []
        temp = n
        for i in range(2, int(-(-n**0.5//1))+1):
            if temp%i==0:
                cnt=0
                while temp%i==0:
                    cnt+=1
                    temp //= i
                arr.append([i, cnt])

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

        return arr
        
    cl = factorization(M)
    
    def combinations(x,y,N):
        fac = [0]*(N+1)
        fac[0],fac[1] = 1,1
        invfac = copy.deepcopy(fac)
        
        for i in range(2,N+1):
            fac[i] = (fac[i-1]*i)%MOD
            
        invfac[-1] = pow(fac[-1],MOD-2,MOD)
        
        for i in range(N,0,-1):
            invfac[i-1] = (invfac[i]*i)%MOD
            
        return (fac[x+y]*invfac[x]*invfac[y])%MOD
        
    ans = 1
    for pr,num in cl:
        ans *= combinations(N-1,num,N+num)
        ans %= MOD
    
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    N,M = map(int,input().split())
    MOD = 10**9+7
    
    def factorization(n):
        arr = []
        temp = n
        for i in range(2, int(-(-n**0.5//1))+1):
            if temp%i==0:
                cnt=0
                while temp%i==0:
                    cnt+=1
                    temp //= i
                arr.append([i, cnt])

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

        return arr
        
    cl = factorization(M)
    
    def combinations(x,y,N):
        fac = [0]*(N+1)
        fac[0],fac[1] = 1,1
        
        for i in range(2,N+1):
            fac[i] = (fac[i-1]*i)%MOD
            
        return (fac[x+y]*pow(fac[x],MOD-2,MOD)*pow(fac[y],MOD-2,MOD))%MOD
        
    ans = 1
    for pr,num in cl:
        ans *= combinations(N-1,num,N+num)
        ans %= MOD
    
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
l = []
i = 2
if m == 1 or n == 1:
    print(1)
    exit()
while m != 1:
    if m%i == 0:
        l.append(0)
        while m%i == 0:
            l[-1] += 1
            m //= i
    i += 1

mod = 10**9+7 
fact = [1,1]
finv = [1,1]
inv = [0,1]
 
for i in range(2,n+max(l)+5):
    fact.append((fact[-1]*i)%mod)
    inv.append((inv[mod%i]*(mod-mod//i))%mod)
    finv.append((finv[-1]*inv[-1])%mod)
 
def nCr(n,r,mod):
    if r > n:
        return 0
    else: 
        return fact[n]*finv[r]*finv[n-r]%mod

ans = 1

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

Submission status: Accepted

Solution code:
"""
---アルゴリズム概要---
a1 ~ anの各スロットに、Mの各素因数をいくつ置くか、という問題。
まずは、Mを素因数分解し、それから重複組み合わせの容量で、各素因数ごとに配分パターンを算出。
それらの配分パターンを素因数間でかけ合わせると、答えとなる。

Mの素因数分解は、試し割り法という最もシンプルな方法で行う。
"""
from collections import Counter
import math
N,M = map(int,input().split())
factors = []
while True:
    if M % 2 == 0:
        M //= 2
        factors.append(2)
    else:
        break
f = 3
while f**2 <= M:
    if M % f == 0:
        M //= f
        factors.append(f)
    else:
        f += 2
if M != 1:
    factors.append(M)

counter = Counter(factors)
ans = 1
for r in counter.values():
    ans *= math.factorial(N+r-1)//(math.factorial(N-1)*math.factorial(r))

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

Submission status: Accepted

Solution code:
import math

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

MOD = 10**9+7

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

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

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

    return arr

fact = factorization(M)

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

else:


  for i in range(len(fact)):
    ans *= ( math.factorial(N-1+fact[i][1]) ) // ( (math.factorial(N-1)) * (math.factorial(fact[i][1])) ) % MOD
    ans = ans%MOD

  print(ans)

Submission status: Accepted

Solution code:
"""
---アルゴリズム概要---
Mを素因数分解する。
各素因数をa1 ~ an をどの場所にいくつ納めるかを考えれば、それが答えになる。
"""
import math
from collections import Counter
N,M = map(int,input().split())
a = []
def prime_factorize(n):
        while n % 2 == 0:
            a.append(2)
            n //= 2
        f = 3
        while f * f <= n:
            if n % f == 0:
                a.append(f)
                n //= f
            else:
                f += 2
        if n != 1:
            a.append(n)
        return a

prime_factorize(M)
#次に各要素の配置パターン数を求めて累積していく。
#combination関数を定義する
def combination(n,r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))

factors = Counter(a)
ans = 1
for k,v in factors.items():
    ans *= combination(N+v-1,v)

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

Submission status: Accepted

Solution code:

def resolve():
    # nCk = n! / n!(n-k)! のテーブル作成
    def COMinit(n, MOD):
        fact = [1, 1]
        fact_inv = [1, 1]
        inv = [0, 1]
        for i in range(2, n + 1):
            fact.append((fact[-1] * i) % MOD)
            inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
            fact_inv.append((fact_inv[-1] * inv[i]) % MOD)
        return fact, fact_inv

    # 二項係数計算
    def Combination(n, k, MOD=10 ** 9 + 7):
        fac, finv = COMinit(n, MOD)
        if n < k: return 0
        if n < 0 or k < 0: return 0
        ret = fac[n] * finv[k] * finv[n - k] % MOD
        return ret

    #指数:exponent
    def dic_factorization(n):
        arr = []
        temp = n
        for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
            if temp % i == 0:
                cnt = 0
                while temp % i == 0:
                    cnt += 1
                    temp //= i
                arr.append([i, cnt])
        if temp != 1:
            arr.append([temp, 1])
        if arr == []:
            arr.append([n, 1])
        return arr

    MOD = 10**9+7
    N, M = map(int, input().split())
    if M==1:
        print(1)
        return
    
    fact = dic_factorization(M)
    ans = 1
    for v in fact:
        ans *= Combination(N+v[1]-1, v[1])
        ans %= MOD

    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr
  
n,m = map(int,input().split())
chk = factorization(m)
from scipy.misc import comb

mod = 10**9+7
ans = 1
if m > 1:
  for i in chk:
    ans *= comb(i[1]+n-1,i[1],mod)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr
  
n,m = map(int,input().split())
chk = factorization(m)

def make_array_for_comb(N, mod=10**9+7):
    fact = [1,1]
    fact_inv = [1,1]
    inv = [0,1]
    for i in range(2, N+1):
        fact.append((fact[-1]*i) % mod)
        inv.append((-inv[mod%i] * (mod//i)) % mod)
        fact_inv.append((fact_inv[-1]*inv[i]) % mod)
    return fact, fact_inv

def comb(n, r, mod=10**9+7):
  if (r < 0) or (n < r):
      return 0
  r = min(r, n - r)
  return fact[n] * fact_inv[r] * fact_inv[n-r] % mod

mod = 10**9+7
ans = 1
for i in chk:
  fact, fact_inv = make_array_for_comb(i[1]+n-1,mod)
  ans *= comb(i[1]+n-1,i[1],mod)
  ans %= mod
if m == 1:
  ans = 1
print(ans)

Submission status: Accepted

Solution code:
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr
  
n,m = map(int,input().split())
chk = factorization(m)
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod) 
  
def comb(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

mod = 10**9+7
ans = 1
for i in chk:
  ans *= comb(i[1]+n-1,i[1],mod)
  ans %= mod
if m == 1:
  ans = 1
print(ans)

Submission status: Accepted

Solution code:
import collections
def modpow(a,n,p):
    if n==0:
        return 1
    x=modpow(a,n//2,p)
    x=(x*x)%p
    if (n%2)==1:
        x=(x*a)%p
    return x%p
def modinv(a,p):
    return modpow(a,p-2,p)
N,M=map(int,input().split())
l=[]
pf={}
m=M
p=10**9+7
frac=[1]*(2*(10**7))
ans=1
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
#print(pf)
for i in range(1,2*(10**7)):
    frac[i]=(frac[i-1]*i)%p
#print(frac[:7])
keys=list(pf.keys())
values=list(pf.values())
for i in range(len(keys)):
    l.append([keys[i],values[i]])
#print(l)
for i in range(len(l)):
    a=l[i][1]
    ans=(ans*frac[a+N-1]*modinv(frac[a],p)*modinv(frac[N-1],p))%p
print(ans%p)