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: Time Limit Exceeded

Solution code:
import math


mod = 10**9 + 7


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


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


n, m = map(int, input().split())
res = 1
fct = factorize(m)

for _, count in fct:
    res = res * combinations_count(n+count-1, count) % mod

print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

# 階上の計算
from math import factorial

def prime_decomposition(n):
  i = 2
  table = []

  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(i)
    i += 1

  if n > 1:
    table.append(n)

  return list(Counter(table).values())

def nHr(n, r):
    return factorial(n+r-1) // (factorial(r) * factorial(n-1))


mod = 10 ** 9 + 7

ans = 1

prim_d_num = prime_decomposition(M)

for p in prim_d_num:
    ans *= nHr(p+1, N-1)

print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7

def hurui(n):
  data = [i for i in range(2, n + 1)]
  for d in data:
    data = [x for x in data if (x == d or x % d != 0)]
  return data

MAX = 10**5 + 100

fac = [1]*(MAX+1)
for i in range(1,MAX+1):
    fac[i] = (fac[i-1]*i)%mod

rev_m = [1]*(MAX+1)
rev_m[MAX] = pow(fac[MAX],mod-2,mod)
for i in range(MAX,0,-1):
    rev_m[i-1] = (rev_m[i]*i)%mod

def Comb(n,k):#nCk
    return (fac[n]*rev_m[k]*rev_m[n-k])%mod


N,M = map(int, input().split())
Primes = hurui(4000)
kk = [0]*4000

while M > 1:
  for i,p in enumerate(Primes):
    if M%p == 0:
      kk[i]+=1
      M//=p
      break

ans =1
for k in kk:
  ans *= Comb(k+N-1,k)
  ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import copy
s=0
n, m=map(int, input().split())
mm = copy.copy(m)
t = {}
a = int(math.sqrt(mm))

while s==0:
    for i in range(2,a+2):
        if m%i==0:
            m=m//i
            if m==1:
                s=1
            if i in t.keys():
                t[i]+=1
            else:
                t[i]=1
            break
out=1

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

for tk in t.keys():
    out *= combi(t[tk]+n-1, n-1)
print(out%(1000000007))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

A = defaultdict(int)
p = 10 ** 9 + 7

i = 2

def fact(n, p=10**9 + 7):
    f = [1]
    for i in range(1, n+1):
        f.append(f[-1]*i%p)
    return f

def invfact(n, f, p=10**9 + 7):
    inv = [pow(f[n], p-2, p)]
    for i in range(n, 0, -1):
        inv.append(inv[-1]*i%p)
    return inv[::-1]

f = fact(30+10**5)
invf = invfact(30+10**5, f)

while m % i == 0:
    m //= i
    A[i] += 1

i += 1

while m != 1:
    while m % i == 0:
        m //= i
        A[i] += 1
    i += 2

n -= 1
ans = 1

for v in A.values():
    ans *= f[v+n] * invf[n] * invf[v] % p
    ans %= p

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

def yakusu(i):
    num = i
    yakusuu_array = []

    for i in range(1, num):
        if num % i == 0:
            yakusuu_array.append(i)
    return yakusuu_array

def calcElem(elem):
    ans = elem[0]
    for i in elem[1:]:
        ans *= i
    return ans


inputs =  list(map(int, input().split()))
N = inputs[0]
M = inputs[1]

yakusuList = yakusu(M)
yakusuList.append(M)

num = 0

for elem in itertools.product(yakusuList, repeat= N):
    if calcElem(elem) == M:
        num+=1

print(num)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def factorial_memo(n, p):
  F = [1] * (n + 1)
  for i in range(n):
    F[i + 1] = F[i] * (i + 1) % p
  return F

def inverse(F, p):
  Finv = [x for x in F]
  Finv[-1] = pow(Finv[-1], p - 2, p)
  for i in range(len(F) - 2, 0, -1):
    Finv[i] = Finv[i + 1] * (i + 1) % p
  return Finv

def comb(*A):
  f = F[sum(A)]
  for a in A:
    f *= Finv[a]
  return f % p

def is_prime(n):
  for prime in prime_table:
    if n % prime == 0:
      return False
  else:
    return True

N, M = map(int, input().split())
p = 10 ** 9 + 7
prime_table = []
primes = defaultdict(int)
primes[1] = 0
n = 2
while n <= M:
  if is_prime(n):
    prime_table.append(n)
    while M % n == 0:
      primes[n] += 1
      M //= n
  n += 1
F = factorial_memo(max(primes.values()) + N, p)
Finv = inverse(F, p)
cnt = 1
for c in primes.values():
  cnt *= comb(c, N - 1)
print(cnt % p)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7

def hurui(n):
  data = [i for i in range(2, n + 1)]
  for d in data:
    data = [x for x in data if (x == d or x % d != 0)]
  return data

MAX = 10**5 + 100

fac = [1]*(MAX+1)
for i in range(1,MAX+1):
    fac[i] = (fac[i-1]*i)%mod

rev_m = [1]*(MAX+1)
rev_m[MAX] = pow(fac[MAX],mod-2,mod)
for i in range(MAX,0,-1):
    rev_m[i-1] = (rev_m[i]*i)%mod

def Comb(n,k):#nCk
    return (fac[n]*rev_m[k]*rev_m[n-k])%mod


N,M = map(int, input().split())
Primes = hurui(8000)
kk = [0]*8000

while M > 1:
  for i,p in enumerate(Primes):
    if M%p == 0:
      kk[i]+=1
      M//=p
      break

ans =1
for k in kk:
  ans *= Comb(k+N-1,k)
  ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

A = defaultdict(int)
p = 10 ** 9 + 7

i = 2

def fact(n, p=10**9 + 7):
    f = [1]
    for i in range(1, n+1):
        f.append(f[-1]*i%p)
    return f

def invfact(n, f, p=10**9 + 7):
    inv = [pow(f[n], p-2, p)]
    for i in range(n, 0, -1):
        inv.append(inv[-1]*i%p)
    return inv[::-1]

f = fact(30+10**5)
invf = invfact(30+10**5, f)

while m != 1:
    while m % i == 0:
        m //= i
        A[i] += 1
    i += 1

n -= 1
ans = 1

for v in A.values():
    ans *= f[v+n] * invf[n] * invf[v] % p
    ans %= p

print(ans)

Submission status: Time Limit Exceeded

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

def devide(n):
    ans=[]
    for i in range(1,n//2+1):
        if n%i==0: ans.append(i)
    ans.append(n)
    return ans
        
def Count(n,m):
    if m==1 or n==1: return 1
    else:
        ans=0
        for d in devide(m):
            ans += Count(n-1,m//d)
        return ans
        
print(Count(N,M))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

def hurui(n):
  data = [i for i in range(2, n + 1)]
  for d in data:
    data = [x for x in data if (x == d or x % d != 0)]
  return data

MAX = 2*(10**5)

fac = [1]*(MAX+1)
for i in range(1,MAX+1):
    fac[i] = (fac[i-1]*i)%mod

rev_m = [1]*(MAX+1)
rev_m[MAX] = pow(fac[MAX],mod-2,mod)
for i in range(MAX,0,-1):
    rev_m[i-1] = (rev_m[i]*i)%mod

def Comb(n,k):#nCk
    return (fac[n]*rev_m[k]*rev_m[n-k])%mod


N,M = inpl()
Primes = hurui(10000)
kk = [0]*10000

while M > 1:
  for i,p in enumerate(Primes):
    if M%p == 0:
      kk[i]+=1
      M//=p
      break
      
ans =1
for k in kk:
  ans *= Comb(k+N-1,k)
  ans %= mod
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import defaultdict

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

A = defaultdict(int)
p = 10 ** 9 + 7

i = 2

def fact(n, p=10**9 + 7):
    f = [1]
    for i in range(1, n+1):
        f.append(f[-1]*i%p)
    return f

def invfact(n, f, p=10**9 + 7):
    inv = [pow(f[n], p-2, p)]
    for i in range(n, 0, -1):
        inv.append(inv[-1]*i%p)
    return inv[::-1]

f = fact(30+10**5)
invf = invfact(30+10**5, f)

def comb(a, b):
    return f[a] * invf[b] * invf[a-b] % p

while m != 1:
    while m % i == 0:
        m //= i
        A[i] += 1
    i += 1

n -= 1
ans = 1

for v in A.values():
    ans *= comb(v+n, n)
    ans %= p

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math
from math import factorial

# K = int(input())
# N, K = map(int, input().split())
# A = list(map(int, input().split()))
# S = input() # String

mod = 1000000000 + 7

def dupcomb(n, k, p):
    return comb(n+k-1, k, p)

def comb(n,k,p):
    if n<0 or k<0 or n<k: return 0
    if n==0 or k==0: return 1
    a=factorial(n) %p
    b=factorial(k) %p
    c=factorial(n-k) %p
    return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p

def power_func(a,b,p):
    if b==0: return 1
    if b%2==0:
        d=power_func(a,b//2,p)
        return d*d %p
    if b%2==1:
        return (a*power_func(a,b-1,p ))%p


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

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

primes = factorize(M)

count = 1

fk_save = dict()

for pair in primes:
    k = pair[1]
    # print('k=', k)

    if k in fk_save:
        fk = fk_save[k]
    else:
        fk = dupcomb(N, k, mod)
        fk_save[k] = fk
    # print('fk=', fk)

    count = (fk * count) % mod
    # print('count=', count)
    
print(count)
# ret = comb(10, 5, mod)
# print(ret)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

def hurui(n):
  data = [i for i in range(2, n + 1)]
  for d in data:
    data = [x for x in data if (x == d or x % d != 0)]
  return data

MAX = 3*(10**5)

fac = [1]*(MAX+1)
for i in range(1,MAX+1):
    fac[i] = (fac[i-1]*i)%mod

rev_m = [1]*(MAX+1)
rev_m[MAX] = pow(fac[MAX],mod-2,mod)
for i in range(MAX,0,-1):
    rev_m[i-1] = (rev_m[i]*i)%mod

def Comb(n,k):#nCk
    return (fac[n]*rev_m[k]*rev_m[n-k])%mod


N,M = inpl()
Primes = hurui(10000)
kk = [0]*10000

while M > 1:
  for i,p in enumerate(Primes):
    if M%p == 0:
      kk[i]+=1
      M//=p
      break
      
ans =1
for k in kk:
  ans *= Comb(k+N-1,k)
  ans %= mod
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math
from math import factorial

# K = int(input())
# N, K = map(int, input().split())
# A = list(map(int, input().split()))
# S = input() # String

mod = 1000000000 + 7

def dupcomb(n, k, p):
    return comb(n+k-1, k, p)

def comb(n,k,p):
    if n<0 or k<0 or n<k: return 0
    if n==0 or k==0: return 1
    a=factorial(n) %p
    b=factorial(k) %p
    c=factorial(n-k) %p
    return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p

def power_func(a,b,p):
    if b==0: return 1
    if b%2==0:
        d=power_func(a,b//2,p)
        return d*d %p
    if b%2==1:
        return (a*power_func(a,b-1,p ))%p


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

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

primes = factorize(M)

count = 1

for pair in primes:
    k = pair[1]
    # print('k=', k)
    fk = dupcomb(N, k, mod)
    # print('fk=', fk)

    count = (fk * count) % mod
    # print('count=', count)
    
print(count)
# ret = comb(10, 5, mod)
# print(ret)

Submission status: Time Limit Exceeded

Solution code:
import math
s=0
n, m=map(int, input().split())
mm = int(m)
t = {}

while s==0:
    for i in range(2,int(math.sqrt(mm))):
#         print(i)
        if m%i==0:
            m=m//i
            if m==1:
                s=1
            if i in t.keys():
                t[i]+=1
            else:
                t[i]=1
            break
out=1
def combi(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r)) 

for tk in t.keys():
    out *= combi(t[tk]+n-1, n-1)
print(out%(1000000007))

Submission status: Time Limit Exceeded

Solution code:
import math

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

def C(n, r):
    return P(n, r)//math.factorial(r)

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


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

facts = factorize(M)
# print(facts)

ans = 1

for fact in facts:
    a = fact[1]
    ans *= C(a+N-1, N-1)
    ans %= 10**9 + 7

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

def prime_factors(n):
	i = 2
	factors = []
	while i * i <= n:
		if n % i:
			i += 1
		else:
			n //= i
			factors.append(i)
	if n > 1:
		factors.append(n)
	return factors
	

a = input().split()
a = [int(i) for i in a]

num = dict()
for i in prime_factors(a[1]):
	if i not in num:
		num[i] = 1
	else:
		num[i] += 1
		
ans = 1
for j in num.values():
	ans *=  (math.factorial(j + a[0] - 1)//(math.factorial(a[0] - 1)* math.factorial(j)))
	ans %= (10**9 + 7)
	
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import groupby
from math import factorial


def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors


def comb(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))


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

for k, g in groupby(prime_factors(M)):
    result = result * comb(len(list(g)) + N - 1, N - 1)
    result = result % (10 ** 9 + 7)

print(result)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


def prepare(n, MOD):
    f = 1
    factorials = [1] * (n + 1)
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials[m] = f
    inv = pow(f, MOD - 2, MOD)
    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


def prime_factorize(n):
    f = defaultdict(lambda: 0)
    f[2] = len(bin(n & -n)) - 3
    i = 3
    k = n >> f[2]
    while k > 1:
        while True:
            d, m = divmod(k, i)
            if m == 0:
                f[i] += 1
                k = d
            else:
                break
        i += 2
    return f


MOD = 1000000007
n, m = map(int, input().split())
pf = prime_factorize(m)
mx = max(pf.values())
f, r = prepare(n + mx - 1, MOD)
ans = 1
for p, e in pf.items():
    ans *= f[n + e - 1]
    ans %= MOD
    ans *= r[n - 1]
    ans %= MOD
    ans *= r[e]
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    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


def prime_factorize(n):
    f = defaultdict(lambda: 0)
    f[2] = len(bin(n & -n)) - 3
    i = 3
    k = n >> f[2]
    while k > 1:
        while True:
            d, m = divmod(k, i)
            if m == 0:
                f[i] += 1
                k = d
            else:
                break
        i += 2
    return f


MOD = 1000000007
n, m = map(int, input().split())
pf = prime_factorize(m)
mx = max(pf.values())
f, r = prepare(n + mx, MOD)
ans = 1
for p, e in pf.items():
    ans *= f[n + e - 1] * r[n - 1]
    ans %= MOD
    ans *= r[e]
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

factorial=[1 for i in range(10**6)]
for i in range(2,10**6):
    factorial[i] = factorial[i-1]*i % mod

def comb(n,k):
    return (factorial[n]*pow(factorial[n-k]*factorial[k], -1, mod))%mod

def factorize(n):
    out=[]
    i = 2
    while 1:
        if n%i==0:
            out.append(i)
            n //= i
        else:
            i += 1
        if n == 1:break
        if i > int(n**.5+3):
            out.append(n)
            break
    
    return out
  
c = Counter(factorize(M))

ans = 1
for k in c.keys():
  ans *= comb(c[k]+N-1,N-1)
  ans %= mod
  
print(ans)

Submission status: Accepted

Solution code:
import math
def fac(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
def com(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
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
a,b = map(int,input().split())
l = fac(b)
for i in l:
  ans *= cmb(i[1]+a-1,a-1)
  ans = ans % (10**9 + 7)
if b == 1:
  print(1)
else:
  print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = 10**6#float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

		
#階乗#
lim = 2*10**5   #必要そうな階乗の限界を入力
fact = [1] * (lim+1)
for n in range(1, lim+1):
	fact[n] = n * fact[n-1] % mod

#階乗の逆元#
fact_inv = [1]*(lim+1)
fact_inv[lim] = pow(fact[lim], mod-2, mod)
for n in range(lim, 0, -1):
	fact_inv[n-1] = n*fact_inv[n]%mod

def C(n, r):
	return (fact[n]*fact_inv[r]%mod)*fact_inv[n-r]%mod


#素因数分解
def factorization(n):
	arr = []
	tmp = n
	for i in range(2, int(-(-n**0.5//1))+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])
	if arr == []:
		arr.append([n, 1])
	return arr


N, M = MAP()
if M == 1:
	print(1)
	exit()

arr = factorization(M)
ans = 1
for g, n in arr:
	ans *= C(N-1+n, n)
	ans %= mod

print(ans)

Submission status: Accepted

Solution code:
def factorize(n):
    '''
    素因数分解をする。
    タプルの配列にしようと思ったけど、逐次割り算する過程で次数を増やせないじゃん。
    二重配列?
    dictにしよう。
    '''
    if n == 1:
        raise('n >= 2')
    
    factor = {}
    div = 2
    while True:
        if div * div > n:
            factor[n] = factor.get(n, 0) + 1
            return factor

        if n % div == 0:
            n //= div
            factor[div] = factor.get(div, 0) + 1
        else:
            div += 1




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

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

factor = factorize(m)


max_len = n + 100  # 適宜変更する
mod = 10**9 + 7


def modinv(x):
    '''
    xの逆元を求める。フェルマーの小定理より、 x の逆元は x ^ (mod - 2) に等しい。計算時間はO(log(mod))程度。
    Python標準のpowは割った余りを出すことも可能。
    '''
    return pow(x, mod-2, mod)


# 二項係数の左側の数字の最大値を max_len　とする。nとかだと他の変数と被りそうなので。
# factori_table = [1, 1, 2, 6, 24, 120, ...] 要は factori_table[n] = n!
# 計算時間はO(max_len * log(mod))
modinv_table = [-1] * (max_len + 1)
modinv_table[0] = None  # 万が一使っていたときにできるだけ早期に原因特定できるようにしたいので、Noneにしておく。
factori_table = [1] * (max_len + 1)
factori_inv_table = [1] * (max_len + 1)
for i in range(1, max_len + 1):
    factori_table[i] = factori_table[i-1] * (i) % mod

modinv_table[1] = 1
for i in range(2, max_len + 1):
    modinv_table[i] = (-modinv_table[mod % i] * (mod // i)) % mod
    factori_inv_table[i] = factori_inv_table[i-1] * modinv_table[i] % mod


def binomial_coefficients(n, k):
    '''
    n! / (k! * (n-k)! )
    0 <= k <= nを満たさないときは変な値を返してしまうので、先にNoneを返すことにする。
    場合によっては0のほうが適切かもしれない。
    '''
    if not 0 <= k <= n:
        return None
    return (factori_table[n] * factori_inv_table[k] * factori_inv_table[n-k]) % mod


ans = 1
mod = 10**9 + 7
for prime, power in factor.items():
    # ans *= n H power = n+power-1 C power 
    ans *= binomial_coefficients(n+power-1, power)
    ans %= mod

print(ans)

Submission status: Accepted

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


# コンビネーション、さらに高速。あらかじめO(N)の計算をすることでのちの計算が早くなる
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
g1=[1,1] # g1[i]=i! % mod　:階乗
g2=[1,1] # g2[i]=(i!)^(-1) % mod　:階乗の逆元
inverse=[0,1]
for i in range(2,min(2*10**5,n+m)+1):
  g1.append((g1[-1]*i)%mod)
  inverse.append((-inverse[mod%i]*(mod//i))%mod)
  g2.append((g2[-1]*inverse[-1])%mod)

#heap

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
#factorization(24) 
## [[2, 3], [3, 1]] 
##  24 = 2^3 * 3^1

if m==1:
  print(1)
  exit()
ary=factorization(m)
ans=1
for x,y in ary:
  ans*=cmb(n-1+y,y,mod)
  ans%=mod
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
mod = 10**9 + 7
# [[素因数,数]]を出力
def fctr1(n):
    f = []
    c = 0
    r = int(n**0.5)
    for i in range(2, r+2):
        while n % i == 0:
            c += 1
            n = n//i
        if c != 0:
            f.append([i, c])
            c = 0
    if n != 1:
        f.append([n, 1])
    return f

def comb(n, r):
    res = 1
    for i in range(1, r+1):
        res = res*(n-i+1) % mod
        res = res*pow(i, mod-2, mod) % mod
    return res

prime_count = fctr1(m)
#print(prime_count)
ans = 1
for p, e in prime_count:
    ans *= comb(e+n-1, e)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict


def comb(n, k, mod=10 ** 9 + 7):
    denominator = 1
    numerator = 1
    for i in range(1, k + 1):
        denominator = denominator * i % mod
    for i in range(n - k + 1, n + 1):
        numerator = numerator * i % mod
    return numerator * pow(denominator, mod - 2, mod) % mod


def main():
    n, m = map(int, input().split())
    factorization = defaultdict(int)
    while not m % 2:
        factorization[2] += 1
        m //= 2
    f = 3
    while f * f <= m:
        if not m % f:
            factorization[f] += 1
            m //= f
        else:
            f += 2
    if m != 1:
        factorization[m] += 1
    ans = 1
    mod = 10 ** 9 + 7
    for _, c in factorization.items():
        ans *= comb(c + n - 1, c, mod)
        ans %= mod
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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


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

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
n = 2*10 ** 5  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p) 階乗のmod
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, n + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

# *////**//
F = factorization(M)

if N==1:
    print(1)
    exit()
if M==1:
    print(1)
    exit()
ans=1
for l in F:
    ans*=cmb(N-1+l[1], l[1], p)
    ans%=p

print(ans)

Submission status: Accepted

Solution code:
mod=10**9+7


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


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


x=factorization(m)

ans=1

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


print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
p=10**9+7
w=[]
M=m
i=2
cnt=0

def f(n,k,p):
    if k==0:
        return 1
    elif k%2==0:
        return (f(n,k//2,p)**2)%p
    else:
        return (n*f(n,k-1,p))%p

while i*i<=M:
    if m%i==0:
        cnt+=1
        m=m//i
    else:
        if cnt>=1:
            w.append(cnt)
        cnt=0
        i+=1
if m>1:
    w.append(1)

ans=1
for x in w:
    a=1
    for i in range(x):
        a=(a*(n+i))%p
    b=1
    for i in range(x):
        b=(b*(i+1))%p

    ans=(ans*a*f(b,p-2,p))%p
print(ans%p)

Submission status: Accepted

Solution code:
def cmb(n, r, p):
  if (r < 0) or (n < r):
    return 0
  r = min(r, n - r)
  return fac[n]*finv[r]*finv[n-r]%p

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

n = 2*pow(10,5)+10
MOD = pow(10,9)+7

fac = [-1]*(n+1); fac[0] = 1; fac[1] = 1 #階乗
finv = [-1]*(n+1); finv[0] = 1; finv[1] = 1 #階乗の逆元
inv = [-1]*(n+1); inv[0] = 0; inv[1] = 1 #逆元
for i in range(2,n+1):
  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 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==[]: #1の場合はここ
        arr.append([n, 1])
 
    return arr


N,M = map(int,input().split())
A = factorization(M)
#print(A)
ans = 1
for X in A:
  if X == [1,1]:
    continue
  k = X[1]
  temp = cmb(k+N-1,k,MOD)
  ans = ans*temp%MOD
print(ans%MOD)

Submission status: Accepted

Solution code:
def nCr(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 #出力の制限
size = 10**6 # size >= n
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
 
for i in range( 2, size + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % 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)
 
    return arr
 
N, M = map(int,input().split())
L = factorization(M)
 
ans = 1
 
for i in L:
    ans *= nCr(i+N-1,N-1,mod)
    ans %= mod
 
print(ans)

Submission status: Accepted

Solution code:
class Factorials:
    def __init__(self, n=10**6, mod=10**9 + 7):
        self.mod = mod

        # self.fac[i] ≡ i! (factorial:階乗)
        self.fac = [1]
        num = 1
        for i in range(1, n+1):
            num *= i
            num %= mod
            self.fac.append(num)

        # self.rec[i] ≡ 1 / i! (reciprocal:逆数)
        num = pow(num, mod-2, mod)
        self.rec = [1 for i in range(n+1)]
        self.rec[n] = num
        for i in range(n-1, 0, -1):
            num *= i + 1
            num %= mod
            self.rec[i] = num

    # comb(n, r) ≡ nCr
    def comb(self, n, r):
        return self.fac[n] * self.rec[r] * self.rec[n - r] % self.mod
    
    # perm(n, r) ≡ nPr
    def perm(self, n, r):
        return self.fac[n] * self.rec[n-r] % self.mod

    # fact(n) ≡ n!
    def fact(self, n):
        return self.fac[n]

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

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

    factors = []
    for i in range(2, m+1):
        if i * i > m:
            if m > 1:
                factors.append(1)
            break

        if m % i == 0:
            num = 1
            m //= i
            while m % i == 0:
                num += 1
                m //= i
            factors.append(num)

    fct = Factorials(n=n+max(factors), mod=mod)

    ans = 1
    for i in factors:
        ans *= fct.comb(n+i-1, i)
        ans %= mod

    print(ans)

main()

Submission status: Accepted

Solution code:
max_n=10**6
mod=10**9+7

frac=[1]
for i in range(1,max_n+1):
  frac.append((frac[-1]*i)%mod)

inv=[1,1]
inv_frac=[1,1]
for i in range(2,max_n):
  inv.append((mod-inv[mod%i]*(mod//i))%mod)
  inv_frac.append((inv_frac[-1]*inv[-1])%mod)
  
def perm(m,n):
  if m<n:
    return 0
  if m==1:
    return 1
  return (frac[m]*inv_frac[m-n])%mod

def comb(m,n):
  if m<n:
    return 0
  if m==1:
    return 1
  return (frac[m]*inv_frac[n]*inv_frac[m-n])%mod




n,m=map(int,input().split())
l=[]
for i in range(2,int(m**0.5)+1):
  if m%i==0:
    c=0
    while m%i==0:
      m//=i
      c+=1
    l.append(c)
if m!=1:
  l.append(1)

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