Problem:


Score : 400 points

Problem Statement

You are given positive integers N and M.

How many sequences a of length N consisting of positive integers satisfy a_1 \times a_2 \times ... \times a_N = M? Find the count modulo 10^9+7.

Here, two sequences a' and a'' are considered different when there exists some i such that a_i' \neq a_i''.

Constraints

All values in input are integers.

1 \leq N \leq 10^5

1 \leq M \leq 10^9

Input

Input is given from Standard Input in the following format:

N M

Output

Print the number of the sequences consisting of positive integers that satisfy the condition, modulo 10^9 + 7.

Sample Input 1

2 6

Sample Output 1

4

Four sequences satisfy the condition: \{a_1, a_2\} = \{1, 6\}, \{2, 3\}, \{3, 2\} and \{6, 1\}.

Sample Input 2

3 12

Sample Output 2

18

Sample Input 3

100000 1000000000

Sample Output 3

957870001



Sample input:
2 6


Sample output:
4

Submission status: Accepted

Solution code:
import math
import collections

Max = 210000
Mod = 1000000007
fac = [0] * Max
finv = [0] * Max
inv = [0] * Max
def COMinit():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, Max):
        fac[i] = fac[i-1] * i % Mod 
        inv[i] = Mod - inv[Mod%i] * (Mod//i) % Mod
        finv[i] = finv[i-1] * inv[i] % Mod 

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

N, M = map(int, input().split())
prime_count = collections.Counter()
for i in range(2, math.ceil(math.sqrt(M))+1):
    while M % i == 0:
        M /= i
        prime_count[i] += 1
if M > 1:
    prime_count[M] += 1

ans = 1
COMinit()
for i, b in prime_count.items():
    tmp = COM(b+N-1, N-1)
    ans = (ans * tmp) % Mod 
print(ans)

Submission status: Accepted

Solution code:
import math

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

def trial_division(n):
  #素因数を格納するリスト
  factor = []
  #2から√n以下の数字で割っていく
  tmp = int(math.sqrt(n)) + 1
  for num in range(2,tmp):
    cnt = 0
    while n % num == 0:
      n //= num
      cnt += 1 
    if cnt != 0:
      factor.append(cnt)
  #リストが空ならそれは素数
  if not factor:
    return []
  else:
    if n != 1:
      factor.append(1)
    return factor

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

ans = 1
cnts = trial_division(M)
for cnt in cnts:
  ans = ans * (cmb(cnt+N-1, cnt))%MOD

# print(cnts)
print(ans)

Submission status: Accepted

Solution code:
import collections
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

def 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 main():
    N, M = map(int, input().split())

    MOD = 10 ** 9 + 7
    c = collections.Counter(prime_factorize(M))
    ans = 1
    for i, j in c.items():
        ans *= cmb(N+j-1,N-1)
        ans %= MOD

    print(ans)

main()

Submission status: Accepted

Solution code:
import math
 
def div(m):
  d = {}
  temp = int(math.sqrt(m))+1
  for i in range(2, temp):
    while m%i== 0:
      m //= i
      if i in d:
        d[i] += 1
      else:
        d[i] = 1
  if d == {}:
    d[m] = 1
  else:
    if m in d:
      d[m] += 1
    elif m != 1:
      d[m] =1
  return d

n, m = map(int, input().split())
if m == 1:
  print(1)
  exit()
#print(div(m))
from math import factorial
d = div(m)
#print(d)
ans = 1
for i in d.values():
  #ans *= int(factorial(i+n-1)) // int(factorial(n-1)) // int(factorial(i))
  ans *= factorial(i+n-1) // factorial(n-1) // factorial(i)
  ans %= 10**9+7
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
MOD=10**9+7
def factorization(n):
    arr = []
    temp = n
    if n==1:
        return arr
    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
arr=factorization(m)
#print(arr)
l=len(arr)
N=30
comb=[1]*31
inv_t = [0]+[1]
for i in range(2,N+1):
  inv_t += [inv_t[MOD % i] * (MOD - int(MOD / i)) % MOD]
for i in range(1,31):
    comb[i]=comb[i-1]*(n-1+i)*inv_t[i]
    comb[i]%=MOD
count=1
for fact,num in arr:
    #print(fact,num,comb[num])
    count*=comb[num]
    count%=MOD
print(count)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce



INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, m = LI()


def mod_comb(n, r, mod=10 ** 9 + 7):
    fact = 1
    for i in range(n - r + 1, n + 1):
        fact = fact * i % mod

    divisor = 1
    for j in range(1, r + 1):
        divisor = divisor * j % mod

    return fact * pow(divisor, mod - 2, mod) % mod


def prime_fac(n):
    table =[]
    i = 2
    while n >= i**2:
    # nのその数自身を除いた素因数は√n以下であることから。
        while n % i == 0:
            table.append(i)
            n //= i
        i += 1
    if n > 1:
        table.append(n)
# 最後に残った、最大の素因数をリストに入れる。
    return table


ans = 1
for k, v in Counter(prime_fac(m)).items():
    ans = ans * mod_comb(v + n - 1, n - 1) % mod



print(ans)

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce
import math
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
import itertools
N,M = [int(x) for x in input().split()]
e = {}
for j in range(2,int(math.sqrt(M)) +2):
  cnt=0
  while M%j==0:
    cnt+= 1
    M = M//j
  if cnt!=0:
    e[j]=cnt
if M!=1:
  e[M]=1


ans = 1
for i in e.values():
  ans *=cmb(i+N-1,i)
  ans %=10**9+7
print(ans)

Submission status: Accepted

Solution code:
#17:33
n,m = map(int,input().split())
mod = 10 ** 9 + 7
i = 2
tmp = 0
fact = []
while i ** 2 <= m:
  if m % i == 0:
    m //= i
    tmp += 1
  else:
    if tmp > 0:
      fact.append(tmp)
    i += 1
    tmp = 0
if m == i:
  tmp += 1
  fact.append(tmp)
else:
  if tmp > 0:
    fact.append(tmp)
  if m > 1:
    fact.append(1)
#print(fact)
ans = 1
def inv(y):
  z = 1
  while y != 1:
    z *= mod // y + 1
    z %= mod
    y = y - mod % y
  return z
#print(inv(5))
for x in fact:
  for j in range(x):
    ans *= n+j
    ans %= mod
    ans *= inv(j+1)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from math import factorial

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

memo = defaultdict(int)
def frac(n, k):
    global memo
    if memo[n] == 0:
        memo[n] = factorial(n)
    if memo[k] == 0:
        memo[k] = factorial(k)
    if memo[n-k] == 0:
        memo[n-k] = factorial(n - k)
    return memo[n] // memo[k] // memo[n-k]

factor = defaultdict(int)

ps = m
for i in range(2, int(m ** 0.5)+1):
    while ps % i == 0:
        ps  = ps // i
        factor[i] += 1
if ps !=1:
    factor[ps] += 1
mod = 10**9+7
result = 1
for i, v in factor.items():
    result = result * frac(n+v-1, v) % mod

print(result)

Submission status: Accepted

Solution code:
n, m = [int(i) for i in input().split()]
prime = 10 ** 9 + 7

def fact(x):
    a = []
    for i in range(2, int(x ** 0.5) + 1):
        if x % i == 0:
            j = 0
            while x % i == 0:
                x //= i
                j += 1
            a.append((i, j))
    if x != 1:
        a.append((x,1))
    return a


f = fact(m)
def kai(x):
    a = 1
    for i in range(a, x + 1):
        a *= i
        a %= prime
    return a

def conv(a, b):
    c = kai(b)
    c *= pow(kai(a), prime - 2, prime)
    c %= prime
    c *= pow(kai(b - a), prime - 2, prime)
    return c % prime


ans = 1
for i in f:
    ans *= conv(n - 1, n + i[1] - 1)
    ans %= prime
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

from collections import Counter

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


#互いに素なa,bについて、a*x+b*y=1の一つの解[x,y]を出力
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return [w[0],w[1]]


#aの逆元(mod M)を求める（aとMは互いに素であることが前提）
def mod_inv(a,M=mod):
    x = extgcd(a,M)[0]
    return (M+x%M)%M


N,M = II()

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

inv = [1]*(N+100)
for i in range(N+100):
    inv[i] = mod_inv(fact[i])

c = Counter(prime_factorize(M))
ans = 1
for k in c.keys():
    i = c[k]
    temp = fact[N-1+i]*inv[i]*inv[N-1]
    ans *= temp
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:

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

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

i = 2
yakusu = [[0, 0]]
num = 0
while i < M**0.5 + 1:
	if M % i == 0:
		num += 1
		M = M // i
		if yakusu[-1][0] == i:
			yakusu[-1][1] += 1
		else:
			yakusu.append([i, 1])
	else:
		num = 0
		i += 1
if M == yakusu[-1][0] and M != 1:
	yakusu[-1][1] += 1
elif M != 1:
	yakusu.append([M, 1])

mod = 1000000007
pow = [1]

def comb(a, b):
	ans = 1
	for i in range(a, b, -1):
		ans *= i
	for i in range(1, a - b + 1):
		ans = ans // i
	ans = ans % mod
	return  ans

total = 1
for i in range(1, len(yakusu)):
	total *= comb(N + yakusu[i][1] - 1, N - 1)
	total = total % mod


print(total)

Submission status: Accepted

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

N, M = map(int,input().split())
mod = 1000000007
def comb(a,b):
    if b > a-b: return comb(a,a-b)
    ansMul = 1
    ansDiv = 1
    for i in range(b):
        ansMul*=a-i
        ansDiv*=i+1
        ansMul%=mod
        ansDiv%=mod
    
    return ansMul * modpow(ansDiv, mod-2) %mod

def modpow(a,p):
    if p==0: return 1
    if p%2==0:
        halfP = p//2
        half = modpow(a,halfP)
        return half*half%mod
    else:
        return a*modpow(a,p-1)

i=2
Mnokori = M
ans=1
while i*i <= Mnokori:
    if Mnokori%i==0:
        cnt=0
        while Mnokori%i==0:
            Mnokori//=i
            cnt+=1
        ans*=comb(cnt+N-1,N-1)
        ans%=mod
    i+=1
if Mnokori!=1:
    ans*=comb(N,N-1)
    ans%=mod  
print(ans%mod)

Submission status: Accepted

Solution code:
import math
import collections

from operator import mul
from functools import reduce

n,m = list(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 #出力の制限
N = 100 + n
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 )



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

c = collections.Counter(prime_factorize(m))
#print(c)
ans = 1
for i,j in c.items():
    ans *= cmb(n+j-1,j,mod) % mod
print(int(ans%mod))

Submission status: Accepted

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

def combo(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    else:
        r = min(r, n-r)
        return g1[n] * g2[r] * g2[n-r] % mod



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

#print(combo(2,1))

#print(m)
fac = {}
mm = m
#print(mm)
count = 0
while mm % 2 == 0:
    count += 1
    mm //= 2
if count > 0:
    fac[2] = count
f = 3
count = 0
while f ** 2 <= mm:
    while mm % f == 0:
        count += 1
        mm //= f
        #print(f,count)
    if count > 0:
        fac[f] = count
        count = 0
    f += 2
    #print(fac)
if mm != 1:
    if mm in fac:
        fac[mm] += 1
    else:
        fac[mm] = 1
#print(fac)

count = 1

for i in fac:
    if fac[i] >= 1:
        count = (count * combo(fac[i]+n-1,fac[i],mod)) % mod
    #print(count)
    
print(count)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N,M = map(int, input().split())
    mod = 10**9 + 7
    MAX = 2*10**5
    kaijo = [1]*MAX
    for i in range(2,MAX):
        kaijo[i] = (kaijo[i-1] * i)%mod
    
    if M == 1:
        print(1)
        sys.exit()
    
    def p_prime(n): 
        prime = [2]
        for i in range(3,n+1):
            flag = 0
            for j in prime:
                if i%j == 0:
                    flag = 1
                    break
                if i**0.5 < j:
                    break
            if flag == 0:
                prime.append(i)
        return prime
    prime = p_prime(10**5)
    
    a = {}
    for p in prime:
        count = 0
        while M%p ==0:
            count += 1
            M //= p
        if count > 0:
            a[p] = count
    if M != 1:
        a[M] = 1
    ans = 1
    for p in a:
        i = a[p]
        ans = (ans * kaijo[i+N-1])%mod
        ans = (ans * pow(kaijo[i],mod-2,mod))%mod
        ans = (ans * pow(kaijo[N-1],mod-2,mod))%mod
    print(ans)
    
    
main()

Submission status: Accepted

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

MAX = 300000
MOD = 1000000007
fac = [0]*MAX
finv = [0]*MAX
inv = [0]*MAX
fac[0] = 1
fac[1] = 1
finv[0] = 1
finv[1] = 1
inv[1] = 1
for i in range(2, MAX):
  fac[i] = fac[i-1]*i%MOD
  inv[i] = MOD - inv[MOD%i]*(MOD//i)%MOD
  finv[i] = finv[i-1]*inv[i]%MOD
def COM(n, k):
  if n < 0 or k < 0 or n < k:
    return 0
  return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD

fs = []
n = M
c = 2
while n > 1:
  if c*c > n:
    fs.append(n)
    break
  if n%c == 0:
    n = n//c
    fs.append(c)
  else:
    c += 1
#print(fs)
Ns = {}
for f in fs:
  if not(f in Ns):
    Ns[f] = 0
  Ns[f] += 1
r = 1
for f in Ns:
  n = Ns[f]
  r = r*COM(N-1+n, n)%MOD
print(r)

Submission status: Accepted

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

def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct

mf = factorize(m)
from collections import Counter

c = Counter(mf)
ans = 1
from scipy.misc import comb
for i in list(c.values()):
  ans*= comb((i+(n-1)),i,exact=True)

print(int(round(ans))%mod)

Submission status: Accepted

Solution code:
import math
n, m = map(int, input().split())
mod = 1000000007
def prime(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for j in range(4, n+1, 2):
        is_prime[j] = False
    for i in range(3, int(n**0.5) + 1, 2):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

def nCr(n, r):
    r = min(r, n - r)
    if r == 0: return 1;
    if r == 1: return n;
    numerator = [n - r + i + 1 for i in range(r)]
    denominator  = [i + 1 for i 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 *= numerator[k] % mod
    return result

def nHr(n, r):
    return nCr(n+r-1, r)

prime_list = prime(int(math.sqrt(m)))
divisor_list = {}
while m > 1:
    for i in prime_list:
        if m % i == 0:
            if i in divisor_list:
                divisor_list[i] = divisor_list[i] + 1
            else:
                divisor_list[i] = 1
            m = m // i
            break
        if i == prime_list[-1]:
            divisor_list[m] = 1
            m = 1
            break
ans = 1
for k in divisor_list:
    ans *= nHr(n, divisor_list[k]) % mod
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
def input():
    return sys.stdin.readline()[:-1]

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

def trial_division(n):
    factor = []
    tmp = int(math.sqrt(n)) + 1
    for num in range(2,tmp):
        while n % num == 0:
            n //= num
            factor.append(num)
    if n!=1:
        factor.append(n)
    return factor

n,m=map(int,input().split())
mod=10**9+7
if m==1:
    print(1)
    quit()
li=trial_division(m)
tmp=li[0]
countli=[]
count=1
for i in range(1,len(li)):
    if tmp!=li[i]:
        countli.append(count)
        count=1
    else:
        count+=1
    tmp=li[i]
countli.append(count)
ans=1
for i in range(len(countli)):
    r=countli[i]
    s=n+r-1
    r=min(r,n-1)
    p=1
    for j in range(r):
        p*=s-j
        p//=j+1
    ans*=p
    ans%=mod
    
print(ans%mod)

Submission status: Accepted

Solution code:
import sys
import math
def input():
    return sys.stdin.readline()[:-1]

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

def trial_division(n):
    factor = []
    tmp = int(math.sqrt(n)) + 1
    for num in range(2,tmp):
        while n % num == 0:
            n //= num
            factor.append(num)
    if n!=1:
        factor.append(n)
    return factor

n,m=map(int,input().split())
mod=10**9+7
if m==1:
    print(1)
    quit()
li=trial_division(m)
tmp=li[0]
countli=[]
count=1
for i in range(1,len(li)):
    if tmp!=li[i]:
        countli.append(count)
        count=1
    else:
        count+=1
    tmp=li[i]
countli.append(count)
ans=1
for i in range(len(countli)):
    ans*=combinations_count(countli[i]+n-1,countli[i])
print(ans%mod)

Submission status: Accepted

Solution code:
import math
import collections
def main():
    N, M = map(int, input().split())
    mod = pow(10, 9) + 7
    if M == 1: return 1

    ps = factorize(M)
    K = max(ps.values())

    pow1 = [1, 1]
    for i in range(2, N+K+1):
        pow1.append(pow1[-1]*i % mod)

    ref = powerquick(pow1[-1], mod-2, mod) # ((N+K)!)^-1 % mod
    invpow1 = [ref]
    for i in range(N+K, 0, -1):
        invpow1.append(invpow1[-1]*i % mod)
    invpow1 = invpow1[::-1]

    # for i in range(len(pow1)):
    #     print(pow1[i]*invpow1[i] % mod)
    # print(invpow1)
    # print(pow1)

    ans = 1
    for p in ps:
        l = ps[p]
        v = pow1[l+N-1]*invpow1[N-1]*invpow1[l] % mod
        ans = (ans * v) % mod

    # print(factorize(35))
    return ans
    # if M == 1: return 1

def powerquick(x, y, mod):
    if y == 0: return 1
    if y == 1: return x % mod
    if y % 2 == 0:
        return pow(powerquick(x, y//2, mod), 2) % mod
    else:
        return pow(powerquick(x, y//2, mod), 2) * x % mod


def factorize(n):
    ps = collections.defaultdict(int)
    if n == 1: return ps
    if isPrime(n):
        ps[n] += 1
        return ps

    p = 1
    while n > 1:
        while not isPrime(p):
            p += 1
        count = 0
        while n % p == 0:
            count += 1
            n = n // p
        if count > 0:
            ps[p] = count
            if isPrime(n):
                ps[n] += 1
                return ps
        p += 1
    return ps

def isPrime(n):
    if n == 1: return False
    for i in range(2, int(math.sqrt(n)+1)):
        if n % i == 0:
            return False
    return True

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

Submission status: Accepted

Solution code:
import math

N, M = map(int, input().split())
yakusu = dict()
sqrt_M = int(math.sqrt(M))
for i in range(2, sqrt_M + 1):
    count = 0
    while M % i == 0:
        count += 1
        M //= i
    if count > 0:
        yakusu[i] = count
if M > 1:
    yakusu[M] = 1


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


ans = 1
MOD = 10 ** 9 + 7
for n in yakusu.values():
    ans *= nCr(n + N - 1, N - 1)
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

N, M = map(int,input().split())
mod = 10**9+7
d = defaultdict(int)
m = M
while m != 1:
    for i in range(2, int(m**0.5)+1):
        if m % i == 0:
            d[i] += 1
            m //= i
            break
    else:
        d[m] += 1
        m = 1

ans = 1
for k in d.keys():
    r = d[k]
    n = N + r - 1
    r = min(r, N - 1)
    p = 1
    for i  in  range(r):
        p *= n -i
        p //= i + 1
    ans *=p
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
from math import factorial
from operator import mul
from functools import reduce

def comb2(n,r):
    r = min(n - r, r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under

def pff(m):
    pf = {}
    for i in range(2, int(m ** 0.5) + 1):
        while m % i == 0:
            pf[i] = pf.get(i, 0) + 1
            m //= i
    if m > 1: pf[m] = 1
    return pf

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


anst = int(1)
for i in L.values():
    anst *= comb2(i+N-1, i)
    anst = anst%1000000007

ans = anst
print(ans)

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

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

def fact(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

l = fact(m)
ans = 1

if l[0][0] == 1 and len(l) == 1:
    print(1)
    exit()

for i in range(len(l)):
    b = l[i][1]
    ans *= cmb(b+n-1, b)
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
from scipy.misc import*;from collections import*;n,m=map(int,input().split());f=Counter();p=h=1
while p*p<=m:
 p+=1
 while m%p==0:f.update([p]);m//=p
if m-1:f.update([m])
for v in f.values():h=h*sum(int(comb(n,i+1,exact=True)*comb(v-1,i,exact=True))for i in range(min(n,v)))%(10**9+7)
print(h)

Submission status: Accepted

Solution code:
from math import sqrt
from collections import Counter

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

mod = 10**9+7

def factor(n) :
    factors = Counter()
    p = 2
    while p*p <= n :
        while n%p == 0 :
            factors.update([p])
            n //= p
        p += 1
    if n > 1 :
        factors.update([n])
    return factors

def comb(n, r) :
    if n - r < r: r = n - r
    if r < 0: return 0
    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

vv = factor(m).values()
ans = 1
for v in vv :
    a = 0
    for i in range(min(n, v)) :
        a += comb(n, i+1)*comb(v-1, i)
    ans *= a
    ans %= mod
print(ans)

Submission status: Accepted

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

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

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
l=factorization(m)
ans=1
for p,b in l:
    com1=1
    com2=1
    for i in range(b):
        com1*=(b+n-1-i)
        com2*=(1+i)
    ans*=(com1//com2)%mod


print(ans%mod)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
def prime_factorize(N): #素因数分解
    exponent = 0
    while N%2 == 0:
        exponent += 1
        N //= 2
    if exponent: factorization = [[2,exponent]]
    else: factorization = []
    i=1
    while i*i <=N:
        i += 2
        if N%i: continue
        exponent = 0
        while N%i == 0:
            exponent += 1
            N //= i
        factorization.append([i,exponent])
    if N!= 1: factorization.append([N,1])
    assert N != 0, "zero"
    return factorization

SIZE=110000; MOD=10**9+7 #998244353 #ここを変更する

SIZE += 1
inv = [0]*SIZE  # inv[j] = j^{-1} mod MOD
fac = [0]*SIZE  # fac[j] = j! mod MOD
finv = [0]*SIZE # finv[j] = (j!)^{-1} mod MOD
inv[1] = 1
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE):
    inv[i] = MOD - (MOD//i)*inv[MOD%i]%MOD
    fac[i] = fac[i-1]*i%MOD
    finv[i]= finv[i-1]*inv[i]%MOD

def choose(n,r): # nCk mod MOD の計算
    if 0 <= r <= n:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    else:
        return 0
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

#n = int(input())
#n,a = [int(i) for i in readline().split()]
n,m = [int(i) for i in readline().split()]

MOD = 10**9+7

ans = 1
L = prime_factorize(m)
for p,e in L:
    ans *= choose(n-1+e,e)
    ans %= MOD


print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
MOD = int(1e9+7)

N, M = map(int, input().split())
d = defaultdict(int)
m = M
while m != 1:
    for i in range(2, int(m**0.5)+1):
        if m % i == 0:
            d[i] += 1
            m //= i
            break
    else:
        d[m] += 1
        m = 1
ans = 1
for k in d.keys():
    r = d[k]
    n = N + r - 1
    r = min(r, N - 1)
    p = 1
    for i in range(r):
        p *= n - i
        p //= i + 1
    ans *= p
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

# 1 <= k <= n <= 10^7 程度
MAX = 510000
fac = [0] * MAX
finv = [0] * MAX
inv = [0] * MAX

fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2, MAX):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD


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

from collections import defaultdict
n, m = map(int, input().split())

d = defaultdict(int)

i = 2
while m > 1:
    if m % i == 0:
        d[i] += 1
        m = m // i
    else:
        i += 1

for i in range(2, 10**5):
    if m % i == 0:
        d[i] += 1
        m = m // i

ans = 1
for k in d.keys():
    ans *= com(n-1+d[k], d[k])
    ans = (ans % MOD)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, fractions, itertools, collections, heapq

MOD = 1000000007  # type: int

def eratosthenes_sieve(n: int):
    """
    エラトステネスの篩を用いてn以下の素数を求める
    """
    table = [0] * (n + 1)
    prime_list = []
    
    for i in range(2, n + 1):
        if table[i] == 0:
            prime_list.append(i)
            for j in range(i + i, n + 1, i):
                table[j] = 1
    
    return prime_list

def prime_factorization(n: int, prime_list: "List[int]"):
    """
    n: 素因数分解したい数
    prime_list: sqrt(n)までの素数が格納されたリスト
    -------------------
    prime_count: 素因数の個数が入ったCounterオブジェクト
    """
    prime_count = collections.Counter()
    
    for i in prime_list:
        if i * i > n:
            break
        while n % i == 0:
            n /= i
            prime_count[int(i)] += 1
    if n > 1:
        prime_count[int(n)] += 1
    
    return prime_count

def mfact(MAX=200000, MOD=1000000007) -> 'List[int]':
    """
    MAXまでの階乗のmodの配列を返します
    """
    f = [1]
    for i in range(1, MAX):
        f.append(f[-1] * i % MOD)
    return f

def inv(x):
    res = 1
    k = MOD - 2
    y = x
    while (k):
        if(k % 2 == 1):
            res = (res * y) % MOD
        y = (y ** 2) % MOD
        k = k // 2
    return res

def comb(n, k, f):
    a = f[n]
    b = f[n-k]
    c = f[k]
    bc = (b * c) % MOD
    return (a * inv(bc)) % MOD


def solve(N: int, M: int):
    prime_list = eratosthenes_sieve(math.ceil(math.sqrt(M)))
    prime_count = prime_factorization(M, prime_list)
    prime_keys = prime_count.keys()
    res = 1
    f = mfact()
    for k in prime_count.keys():
        res *= comb(prime_count[k]+N-1, prime_count[k], f)
    print(res % MOD)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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:
N,M = map(int,input().split())
ans = [N-1]*int(M**0.5+10)
MOD = 10**9 + 7
p = 2
M_copy = M
while p <= M_copy**0.5:
    if M%p == 0:
        M = M//p
        ans[p] += 1
    else:
        p += 1
if M != 1:
    ans[-1] += 1
out = 1
for r in ans:
    hoge = 1
    for i in range(min(N-1,r-N+1)):
        hoge *= r-i
        hoge //= i+1
    out *= hoge
    out %= MOD
print(out)