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:
# using main() makes code faster from the point of view of "access to variables in global name-space"
# def main():

# for i, a in enumerate(iterable)
# q, mod = divmod(a, b)
# divmod(x, y) returns the tuple (x//y, x%y)
# manage median(s) using two heapq https://atcoder.jp/contests/abc127/tasks/abc127_f
import sys
sys.setrecursionlimit(10**7)
from itertools import accumulate, combinations, permutations # https://docs.python.org/ja/3/library/itertools.html
from math import factorial
def factorize(n):
    """return the factors of the Arg and count of each factor
    
    Args:
        n (long): number to be resolved into factors
    
    Returns:
        list of tuples: factorize(220) returns [(2, 2), (5, 1), (11, 1)]
    """
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct
def combinations_count(n, r):
    # faster than the following code
    # def combinations_count(n, r):
    #     return factorial(n) // (factorial(n - r) * factorial(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
def combination_with_repetition_count(n, r):
    return combinations_count(n + r - 1, r)
from collections import deque, Counter # https://docs.python.org/ja/3/library/collections.html#collections.deque
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest # https://docs.python.org/ja/3/library/heapq.html
from copy import deepcopy, copy # https://docs.python.org/ja/3/library/copy.html
from operator import itemgetter 
# ex1: List.sort(key=itemgetter(1))
# ex2: sorted(tuples, key=itemgetter(1,2))
from functools import reduce
from fractions import gcd # Deprecated since version 3.5: Use math.gcd() instead.
def gcds(numbers):
    return reduce(gcd, numbers)
def lcm(x, y):
    return (x * y) // gcd(x, y)
def lcms(numbers):
    return reduce(lcm, numbers, 1)

# first create factorial_list
# fac_list = mod_factorial_list(n)
INF = 10 ** 18
MOD = 10 ** 9 + 7
modpow = lambda a, n, p = MOD: pow(a, n, p) # Recursive function in python is slow!
def modinv(a, p = MOD):
    # evaluate reciprocal using Fermat's little theorem:
    # a**(p-1) is identical to 1 (mod p) when a and p is coprime
    return modpow(a, p-2, p)
def modinv_list(n, p = MOD):
    if n <= 1:
        return [0,1][:n+1]
    else:
        inv_t = [0,1]
        for i in range(2, n+1):
            inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
        return inv_t
def modfactorial_list(n, p = MOD):
    if n == 0:
        return [1]
    else:
        l = [0] * (n+1)
        tmp = 1
        for i in range(1, n+1):
            tmp = tmp * i % p
            l[i] = tmp
        return l
def modcomb(n, k, fac_list = [], p = MOD):
    # fac_list = modfactorial_list(100)
    # print(modcomb(100, 5, modfactorial_list(100)))
    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    if len(fac_list) <= n:
        a = factorial(n) % p
        b = factorial(k) % p
        c = factorial(n-k) % p
    else:
        a = fac_list[n]
        b = fac_list[k]
        c = fac_list[n-k]
    return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
def modadd(a, b, p = MOD):
    return (a + b) % MOD
def modsub(a, b, p = MOD):
    return (a - b) % p
def modmul(a, b, p = MOD):
    return ((a % p) * (b % p)) % p
def moddiv(a, b, p = MOD):
    return modmul(a, modpow(b, p-2, p))


# initialize variables and set inputs
#initialize variables
    # to initialize list, use [0] * n
    # to initialize two dimentional array, use [[0] * N for _ in range(N)]
# set inputs
    # open(0).read() is a convenient method:
    # ex) n, m, *x = map(int, open(0).read().split())
    #     min(x[::2]) - max(x[1::2])
    # ex2) *x, = map(int, open(0).read().split())
    #     don't forget to add comma after *x if only one variable is used
# calculate and output
    # output pattern
    # ex1) print(*l) => when l = [2, 5, 6], printed 2 5 6

# set test data
# sys.stdin = open('sample.txt') # for test

# functions used
r = lambda: sys.stdin.readline().strip() #single: int(r()), line: map(int, r().split())
R = lambda: list(map(int, r().split())) # line: R(), lines: [R() for _ in range(n)]
Rmap = lambda: map(int, r().split())

# set inputs
N, M = R()
L = factorize(M)
ans = 1
for _, l in L:
    ans *= combination_with_repetition_count(N, l)
    ans = ans % MOD
print(ans)

# if __name__ == '__main__':
#     main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

X = 10**9+7
N,M = list(map(int,input().split()))
def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct

def cmb(n, r):
    # faster than the following code
    # def combinations_count(n, r):
    #     return factorial(n) // (factorial(n - r) * factorial(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


ans = 1
for val,dupes in factorize(M):
    ans *= cmb(N+dupes-1,N-1)
    ans = ans % X
print(ans%X)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

X = 10**9+7
N,M = list(map(int,input().split()))
def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n;

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])%X

    return result%X


ans = 1
for val,dupes in factorize(M):
    ans *= cmb(N+dupes-1,N-1)
    ans = ans % X
print(ans%X)

Submission status: Accepted

Solution code:
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**6
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(int, input().split())
ans = 1
factor_dic = {}
for i in range(2,M):
    count = 0
    while M % i == 0:
        count += 1
        M = M // i
    if count:
        factor_dic[i] = count
        if M == 1:
            break
for key,value in factor_dic.items():
    ans = ans * cmb(N+value-1,value,mod)
    ans = ans % mod
print(ans)

Submission status: Accepted

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

from collections import Counter
 
def soinsuu(n):
    list_=[]
    while(n!=1):
        for i in range(2,int(n**0.5)+1):
            if n%i==0:
                list_.append(i)
                n=n//i
                break
        else:
            list_.append(n)
            n=1
    return sorted(list_)
 
def product(a):
    pro=1
    for b in a:
        pro=pro*b%(10**9+7)
    return pro
 
#n!,nPr,nCrの高速計算
def n_func(n,mod=10**9+7):
    ans=1
    for i in range(1,n+1):
        ans=(ans*i)%mod
    return ans
def inv_n(n,mod=10**9+7):
    return pow(n,mod-2,mod)
def nPr(n,r,mod=10**9+7):
    ans=n_func(n-r,mod)
    ans=inv_n(ans,mod)
    return ans*n_func(n,mod)%mod
def nCr(n,r,mod=10**9+7):
    ans=n_func(n-r,mod)*n_func(r,mod)%mod
    ans=inv_n(ans,mod)
    return ans*n_func(n,mod)%mod
    
p=list(Counter(soinsuu(M)).values())
print(product([nCr(N+p[i]-1,p[i]) for i in range(len(p))]))

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
mod=10**9+7
 
from math import factorial
from collections import Counter
 
def soinsuu(n):
    list_=[]
    while(n!=1):
        for i in range(2,int(n**0.5)+1):
            if n%i==0:
                list_.append(i)
                n=n//i
                break
        else:
            list_.append(n)
            n=1
    return sorted(list_)
 
def product(a):
    pro=1
    for b in a:
        pro=pro*b%mod
    return pro
 
#n!,nPr,nCrの高速計算
def n_func(n,mod=10**9+7):
    ans=1
    for i in range(1,n+1):
        ans=(ans*i)%mod
    return ans
def inv_n(n,mod=10**9+7):
    return pow(n,mod-2,mod)
def nPr(n,r,mod=10**9+7):
    ans=n_func(n-r,mod)
    ans=inv_n(ans,mod)
    return ans*n_func(n,mod)%mod
    
nPr_list=[nPr(N,i) for i in range(30)]
bunbo_list=dict()

def dp(cur,init,seq,lest,num):
    #print(cur,init,seq,lest,num)
    if cur==N:
        if lest==0:
            cnt=sorted(list(Counter(seq).values())+[N-len(seq)],reverse=True)
            bunbo=product(map(factorial,cnt[1:]))
            if bunbo not in bunbo_list.keys():
                bunbo_list[bunbo]=inv_n(bunbo)
            memo[num]=(memo[num]+nPr_list[N-cnt[0]]*bunbo_list[bunbo])%mod
    elif lest==0:
        dp(N,init,seq,0,num)
    else:
        if cur==0:
            for i in range(1,lest+1):
                dp(cur+1,init,seq+[i],lest-i,num)
        else:
            for i in range(1,min(lest,seq[-1])+1):
                dp(cur+1,init,seq+[i],lest-i,num)
 
p=list(Counter(soinsuu(M)).values())
memo=[0]*len(p)


for i in range(len(p)):
    dp(0,p[i],[],p[i],i)
print(product(memo))

Submission status: Accepted

Solution code:
mod=10**9+7
N,M=map(int,input().split())
from collections import defaultdict
yaku=defaultdict(int)
now=M
for i in range(2,1+M):
    if now**0.5<i:
        yaku[now]+=1
        break
    while now%i==0:
        yaku[i]+=1
        now//=i
    if now==1:
        break
kaijo=[0]*(1+N)
kaijo[0]=1
for i in range(1,1+N):
    kaijo[i]=kaijo[i-1]*i%mod
gyaku=[0]*(1+N)
gyaku[N]=pow(kaijo[N],mod-2,mod)
for i in range(N,0,-1):
    gyaku[i-1]=gyaku[i]*i%mod
def calc(N,x):
    dp=defaultdict(list)
    dp[1].append([1])
    for i in range(1,x):
        for L in dp[i]:
            if L[-1]+i<=x:
                dp[i+L[-1]].append(L+[L[-1]])
            M=L.copy()
            M[-1]+=1
            dp[i+1].append(M)
    res=0
    for L in dp[x]:
        if len(L)>N:
            continue
        now=kaijo[N]*gyaku[N-len(L)]%mod
        cnt=defaultdict(int)
        for l in L:
            cnt[l]+=1
        for k,v in cnt.items():
            now=now*gyaku[v]%mod
        res=(res+now)%mod
    return res
ans=1
for k,v in yaku.items():
    ans=ans*calc(N,v)%mod
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

prime = defaultdict(int)
m = M
for i in range(2, 10 ** 5):
    while m % i == 0 and m > 1:
        prime[i] += 1
        m //= i

if m > 1:
    prime[m] = 1
MOD = 10 ** 9 + 7

def comb(n, k):
    a = 1
    for i in range(1, k + 1):
        a *= n - i + 1
        a %= MOD
        
        a *= pow(i, MOD - 2, MOD)
        a %= MOD
        
    return a

ans = 1
for _, t in prime.items():
    ans *= comb(N - 1 + t, t)
    ans %= MOD
    
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

prime = defaultdict(int)
m = M
for i in range(2, 10 ** 5):
    while m % i == 0 and m > 1:
        prime[i] += 1
        m //= i

if m > 1:
    prime[M] = 1
MOD = 10 ** 9 + 7

def comb(n, k):
    a = 1
    for i in range(1, k + 1):
        a *= n - i + 1
        a %= MOD
        
        a *= pow(i, MOD - 2, MOD)
        a %= MOD
        
    return a

ans = 1
for _, t in prime.items():
    ans *= comb(N - 1 + t, t)
    ans %= MOD
    
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

prime = defaultdict(int)
m = M
for i in range(2, 10 ** 5):
    while m % i == 0 and m > 1:
        prime[i] += 1
        m //= i

if m > 1:
    prime[10 ** 9] = 1
MOD = 10 ** 9 + 7

def comb(n, k):
    a = 1
    for i in range(1, k + 1):
        a *= n - i + 1
        a %= MOD
        
        a *= pow(i, MOD - 2, MOD)
        a %= MOD
        
    return a

ans = 1
for _, t in prime.items():
    ans *= comb(N - 1 + t, t)
    ans %= MOD
    
print(ans)

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce

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


def factorization(n):  # => {p:count,...}
    fac = {}
    for i in range(2, int(n ** .5) + 1):
        count = 0
        while n % i == 0:
            n //= i
            count += 1
        if count > 0:
            fac[i] = count
    if n > 1:
        fac[n] = 1
    return fac


def C(n, r , mod):
    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 % mod


ans = 1
for c in factorization(m).values():
    ans *= C(c + n - 1, c, mod)
    ans %= mod
print(ans)

Submission status: Accepted

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


def factorization(n):  # => {p:count,...}
    fac = {}
    for i in range(2, int(n ** .5) + 1):
        count = 0
        while n % i == 0:
            n //= i
            count += 1
        if count > 0:
            fac[i] = count
    if n > 1:
        fac[n] = 1
    return fac


def C(n, r, mod):
    r = min(n - r, r)
    if r == 0:
        return 1
    over = list(range(n, n - r, -1))
    for k in range(2, r + 1):
        fac = factorization(k)
        for key, value in fac.items():
            for _ in range(value):
                for i, o in enumerate(over):
                    if o % key == 0:
                        over[i] //= key
                        break
    ret = 1
    for o in over:
        ret *= o
        ret %= mod
    return ret


ans = 1
for c in factorization(m).values():
    ans *= C(c + n - 1, c, mod)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
mod = 10**9+7
def prime_decomposition(n):
  i = 2
  d = {}
  while i * i <= n:
    while n % i == 0:
      n //= i
      if i not in d:
          d[i] = 0
      d[i] += 1
    i += 1
  if n > 1:
    if n not in d:
        d[n] = 1
  return d
N,M = map(int,input().split())

fact = [1]*(10**6+1)
for n in range(1,10**6+1):
    fact[n] = n*fact[n-1]%mod

d = prime_decomposition(M)

ans = 1
for k in d:
    m = d[k]
    ans *= fact[N+m-1]*pow(fact[m],mod-2,mod)*pow(fact[N-1],mod-2,mod)
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import defaultdict



MOD = 10**9+7
FACTOR = []

def factrial(n):
  global FACTOR
  FACTOR = [1 for _ in range(n+1)]
  for i in range(1,n+1):
    FACTOR[i] = (FACTOR[i-1]*i) % MOD

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

def power(a,b):
  ## 二分累乗法
  if   b==0   : return 1
  elif b==1   : return a % MOD
  elif b%2==0 : return power(a,b//2)**2 % MOD
  else        : return power(a,b//2)**2 * a % MOD

def div(a,b):
  ## MOD同士の割り算
  return mul(a,power(b,MOD-2))

## 素因数分解
def factoring(m):
  fact = defaultdict(lambda:0)
  idx = 2
  while m > idx:
    if m%idx==0:
      fact[idx] += 1
      m //= idx
    else:
      idx += 1
  fact[m] += 1
  ret = []
  for k in fact:
    ret.append(fact[k])
  return ret

def combi(a,b):
  if a<b:
    return 1
  else:
    return div(FACTOR[a], (FACTOR[b]*FACTOR[abs(a-b)])%MOD)


def main():
  N,M = map(int, input().split())
  if N == 1 or M==1:
    print(1)
  else:
    fact = factoring(M)
    factrial(N+max(fact))
    ans = 1
    for f in fact:
      ans = (ans * combi(f+N-1,N-1)) % MOD
    print(ans)


if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:

MOD = int(1e9) + 7

def main():
    buf = input()
    buflist = buf.split()
    N = int(buflist[0])
    M = int(buflist[1])
    if M == 1:
        print(1)
        return
    prime_factor = prime_factorization(M)
    factor_count = []
    for k, v in prime_factor.items():
        factor_count.append(v)
    max_factor = max(factor_count)
    nPr = [1]
    nCr = [1]
    factorial = [1]
    rHn = [1]
    for i in range(N, 0, -1):
        nPr.append((nPr[-1] * i) % MOD)
        nCr.append((nCr[-1] * i * modinv(N - i + 1)) % MOD)
    for i in range(1, N + max_factor + 1):
        factorial.append((factorial[-1] * i) % MOD)
    for i in range(1, max_factor+1):
        rHn.append((factorial[N+i-1] * modinv(factorial[N-1]) * modinv(factorial[i])) % MOD)
    combination = 1
    for x in factor_count:
        # n個のボールをr個の箱に入れる場合の組み合わせ総数は？
        # = rHn
        # = n+r-1Cn
        combination = (combination * rHn[x]) % MOD
    print(combination)


def prime_factorization(x):
    n = x
    i = 2
    factor = {}
    while i * i <= n:
        while n % i == 0:
            if i in factor:
                factor[i] += 1
            else:
                factor.update({i : 1})
            n //= i
        i += 1
    if n > 1 or not factor:
        if n in factor:
            factor[n] += 1
        else:
            factor.update({n : 1})
    return factor

def modinv(x, m = MOD):
    b = m
    u = 1
    v = 0
    while b:
        t = x // b
        x -= t * b
        x, b = b, x
        u -= t * v
        u, v = v, u
    u %= m
    if u < 0:
        u += m
    return u

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
MOD = 10 ** 9 + 7
n, m = map(int, input().split())
fact = [0] * (n + 100)
fact[0] = 1
for i in range(len(fact) - 1):
  fact[i + 1] = fact[i] * (i + 1) % MOD
factor = defaultdict(int)
for num in range(2, int(m ** (1 / 2)) + 1):
  while m % num == 0:
    m //= num
    factor[num] += 1
if m != 1:
  factor[m] += 1
ans = 1
for v in factor.values():
  ans *= (fact[v + n - 1] * pow(fact[n - 1], MOD - 2, MOD) * pow(fact[v], MOD - 2, MOD)) % MOD
print(ans % MOD)

Submission status: Accepted

Solution code:
import math
import collections
def primes(n):
    a = list(range(2, n+1))
    primes = [2]
    for i in a:
        flag = True
        m = math.sqrt(i)
        for j in primes:
            if j > m:
                break
            else:
                if i % j == 0:
                    flag = False
                    break
        if flag:
            primes.append(i)
    return primes
N, M = map(int, input().split())
prime = primes(10**5)
m = math.sqrt(M)
dic = collections.defaultdict(int)
mod = 10**9 + 7
for p in prime:
    if p <= m:
        while M % p == 0:
            dic[p] += 1
            M = M//p
if M > 1:
    dic[M] += 1
def comb(n, k):
    ans = 1
    for i in range(1, k+1):
        ans = ans*(n+1-i)//i
    return ans
ans = 1
for i in dic.values():
    ans *= comb(N+i-1, i)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

def combi(m,n):
    child = 1
    mom = 1
    while n != 0:
        child *= m
        mom *= n
        m -= 1
        n -= 1
    return child//mom

def prime(N):
    se = [0,0,1]+[1]*(N-2)
    n = 2
    while n ** 2 <= N:
        if se[n]:
            nn = 2*n
            while nn <= N:
                se[nn] = 0
                nn += n
        n += 1

    return [x for x in range(0,N+1) if se[x]]

P = prime(31622)

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

d = defaultdict(int)

for p in P:
    while not(M%p):
        M //= p
        d[p] += 1

if M != 1:
    d[M] += 1

ans = 1
for k,v in d.items():
    ans *= combi(N+v-1,v)
    ans %= 10**9+7

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

def combnk_mod(n, k, p):
    # pが素数かつaとpが互いに素であるとき
    # フェルマーの小定理より以下が成り立つ.
    # 1 / a = a ** (p - 2) (mod p)
    # これを使って (1 / k!) mod p を計算する.

    if  2 * k > n:
        k = n - k
    x = 1 # 分母にあたる数 1 / n! mod p
    y = 1 # 分子にあたる数. n! / (n - k)! mod p
    for i in range(1, k + 1):
        x *= pow(i, p - 2, p)
        y *= n - i + 1
        x %= p
        y %= p
    return (x * y) % p

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

for i in range(2, int(m ** 0.5) + 1):
    while(m % i == 0):
        m = m // i
        d[i] += 1
if m > 1:
    d[m] = 1

ans = 1
for i in d.values():
    ans *= combnk_mod(i + n - 1, i, MOD)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
import math
import copy
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
from bisect import bisect_left, bisect_right
# import numpy as np

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]

def i_inpl(): return int(input())
def s_inpl(): return map(int,input().split())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")
MAX_DIGIT = 50

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

        :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):
        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):
        d = n - 1
        while d & 1 == 0:
            d >>= 1

        witnesses = self.get_witnesses(n)

        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):
        p = Prime.seed_primes[seed % len(Prime.seed_primes)]
        return (p * x + seed) % n

    def find_factor(self, n, seed=1):
        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()

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

N, M = l_inpl()
ans = 1
for i, k in prime.find_factors(M).items():
    ans *= cmb(k + N - 1, k) 
    ans %= (int(10e8) + 7)

print(ans % (int(10e8) + 7))

Submission status: Accepted

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

ctr = Counter()
m,r = 2,M
while m*m <= r:
    while r%m==0:
        r //= m
        ctr[m] += 1
    m += 1
if r > 1:
    ctr[r] += 1

MAXN = N+50
MOD = 10**9+7
         
fac = [1,1] + [0]*MAXN
finv = [1,1] + [0]*MAXN
inv = [0,1] + [0]*MAXN
for i in range(2,MAXN+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

def ncr(n,r):
    if n < r: return 0
    if n < 0 or r < 0: return 0
    return fac[n] * (finv[r] * finv[n-r] % MOD) % MOD

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd

MOD = 1000000007  # type: int


def prime_table(n):
    t = [True] * (n + 1)
    t[0] = False
    t[1] = False

    for p in range(2, n + 1, 2):
        if n < p ** 2:
            break
        if t[p]:
            for i in range(p * p, n + 1, 2 * p):
                t[i] = False
    return [2] + [p for p in range(3, n + 1, 2) if t[p]]


def pow_mod(a, k, M):
    if k == 0:
        return 1
    t = pow_mod(a, k // 2, M)
    res = (t * t) % M
    if k % 2 == 1:
        res = (res * a) % M

    return res


def inv_mod(a, M):
    return pow_mod(a, M - 2, M)


def fact_mod(a, M):
    ret = 1
    for i in range(2, a + 1):
        ret = (ret * i) % M
    return ret

def perm_mod(n, m, M):
    ret = 1
    for i in range(n, n - m, -1):
        ret = (ret * i) % M
    return ret


def comb_mod(n, m, M):
    return (perm_mod(n, m, M) * inv_mod(fact_mod(m, M), M)) % M


def solve(N: int, M: int):
    fs = defaultdict(int)
    for p in prime_table(int(M ** 0.5) + 1):
        while (M % p) == 0:
            fs[p] += 1
            M //= p
    if M != 1:
        fs[M] = 1

    ret = 1
    for c in fs.values():
        ret = (ret * comb_mod(c + N - 1, c, MOD)) % MOD

    return ret


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
    result = solve(N, M)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd

MOD = 1000000007  # type: int


def prime_table(n):
    rn = int(ceil(sqrt(n)))
    t = [True] * (rn + 1)
    t[0] = False
    t[1] = False

    i = 2
    while i * i <= n:
        for ii in range(2 * i, rn + 1, i):
            t[ii] = False
        i += 1
    return [x for x, i in enumerate(t) if i == True]


def combination(n, m):
    return reduce(mul, range(n, n - m, -1), 1) // factorial(m)

def solve(N: int, M: int):
    fs = defaultdict(int)
    for p in prime_table(M):
        while (M % p) == 0:
            fs[p] += 1
            M //= p
    if M != 1:
        fs[M] = 1

    ret = 1
    for c in fs.values():
        ret *= combination(c + N - 1, c)

    return ret % MOD


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
    result = solve(N, M)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a1, a2 = 2, M
a = {}
while (a1 - 1) ** 2 <= a2 or a1 == a2:
    if a2 % a1 == 0:
        a2 //= a1
        a[a1] = a.get(a1, 0) + 1
    else:
        a1 += 1
if a2 != 1:
    a[a2] = 1
p = 1
for v in a.values():
    for i in range(v):
        p = p * (v + N - 1 - i) // (i + 1)
print(p % (10 ** 9 + 7))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a1, a2 = 2, M
a = {}
while (a1 - 1) ** 2 <= a2 or a1 == a2:
    if a2 % a1 == 0:
        a2 //= a1
        if a1 in a:
            a[a1] += 1
        else:
            a[a1] = 1
    else:
        a1 += 1
p = 1
if a2 != 1:
    a[a2] = 1
for v in a.values():
    tmp = 1
    for i in range(v):
        tmp = tmp * (v + N - 1 - i) // (i + 1)
    p *= tmp
print(p % (10 ** 9 + 7))

Submission status: Accepted

Solution code:
n,M=map(int,input().split())
i=2
c_list=[]
m=M
while i**2<=M:
    count=0
    while m%i==0:
        m=m//i
        count=count+1
    if not count==0:
        c_list.append(count)
    i=i+1
if not m==1:
    c_list.append(1)
def comb(x,y):
    a=1
    for i in range(x-y+1,x+1):
        a=a*i
    b=1
    for i in range(1,y+1):
        b=b*i
    return a//b
if M==1:
    print(1)
else:
    INF=10**9+7
    Sum=1
    for i in c_list:
        Sum=Sum*comb(i+n-1,i)
        Sum=Sum%INF
    print(Sum)