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:
from collections import defaultdict
import math
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
limit = math.sqrt(M)
prime_table = []
primes = defaultdict(int)
primes[1] = 0
n = 2
while n <= M:
  if n > limit or is_prime(n):
    prime_table.append(n)
    while M % n == 0:
      primes[n] += 1
      M //= n
    limit = math.sqrt(M)
  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:
from collections import defaultdict
import math
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 n > math.sqrt(M) or 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:
import sys

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

factor = {}
tmp = 2
while(M // tmp >= 1):
    if(M % tmp != 0):
        if(tmp == 2):
            tmp += 1
        else:
            tmp += 2
        continue

    M = M // tmp
    factor[tmp] = factor.get(tmp, 0) + 1

if(factor == {}):
    print(1)
    sys.exit()

ans = 1
max_a = 7 + 10 ** 9
max_value = max(list(factor.values()))
aho = {0: 1}
fact = {0: 1}
abc = {}
for i in range(1, max_value + 1):
    # print(i)
    aho[i] = ((aho[i - 1] * (i + N - 1)))
    fact[i] = (fact[i - 1] * i)
    abc[i] = (aho[i] // fact[i]) % max_a


# print(factor)
# print(aho, fact)
for i in factor.values():
    # print(i)
    ans = (ans * abc[i]) % max_a
print(ans)

Submission status: Time Limit Exceeded

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

def factorized(M):
    d = 2
    f = []
    while d <= M:
        count = 0
        while M % d == 0:
            M //= d
            count += 1
        if count > 0:
            f.append(count)
        d += 1
    return f

def tetra(n, m):
    x = 1
    for y in range(1, n):
        x = x * (m + y - 1) // y
    return x

x = 1
for f in factorized(M):
    x *= tetra(N, f + 1)
    x %= 10 ** 9 + 7

print(x)

Submission status: Time Limit Exceeded

Solution code:
import math


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

orig = M

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

def c(n, r):
    return p(n, r) // math.factorial(r)

mp = dict({})

while True:
    if not M % 2 == 0:
        break
    try:
        mp[2] += 1
    except:
        mp[2] = 1
    M //= 2

min = 3
find = True

while find:
    find = False
    i = min
    while i <= math.sqrt(orig):
        if M % i == 0:
            try:
                mp[i]+= 1
            except:
                mp[i] = 1
            min = i
            M //= i
            find = True
            break
        i += 2

if not M == 1:
    try:
        mp[M]+= 1
    except:
        mp[M] = 1

ans = 1

for v in mp.values():
    ans *= c(N + v - 1, v)
    ans %= 1000000007

print(ans)

Submission status: Time Limit Exceeded

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

def make_divisor_list(n):
    if n < 1:
        return []
    elif n == 1:
        return [1]
    else:
        divisor_list = []
        divisor_list.append(1)
        for i in range(2, n // 2 + 1):
            if n % i == 0:
                divisor_list.append(i)
        divisor_list.append(n)

        return divisor_list

n, m = map(int, input().split())
d = []
for i in make_divisor_list(m):
    d += [i] * n
count = 0
ans = []
for v in itertools.permutations(d, n):
    if reduce(mul, v) == m:
        if not v in ans:
            ans.append(v)
            count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from bisect import bisect_right

# nの逆元のリスト
def inv_mod(n:int, mod:int) -> list:
    inv = [0,1]
    for i in range(2,n+1):
        inv.append(mod - ((mod//i)*inv[mod%i]) % mod)
    return inv
       
# nの階乗のリスト
def fact(n:int, mod:int) -> list:
    fac = [1,1]
    res = 1
    for i in range(2,n+1):
        res = res*i%mod
        fac.append(res)
    return fac

# nの階乗の逆元のリスト
def fact_inv(n:int, inv:list, mod:int) -> list:
    facInv = [1,1]
    for i in range(2,n+1):
        facInv.append(facInv[i-1]*inv[i] % mod)
    return facInv
        

from collections import Counter

n,m = li()

MOD = 10**9+7

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


# Mの素因数リストを作る

def cd(n:int):
    m = 2
    cds = set([n])
    while m*m <= n:
        if n%m == 0:
            cds.add(m)
            cds.add(n//m)
            
        m += 1

    return sorted(list(cds))
    
cds = cd(m)

memo = []

def dfs(m: int, cds: list, res:int,st:list):
    if res == 1:
        memo.append(st)
        
    else:
        idx = bisect_right(cds,st[-1])
        for cdi in cds[:idx]:
            if cdi > st[-1]:
                pass
            else:
                if res%cdi == 0:
                    dfs(m,cds,res//cdi,st+[cdi])
                

# 辞書順にmを作れるオリジナルなセットを作る
for cdi in cds:
    dfs(m,cds,m//cdi,[cdi])


ans = 0
for memoi in memo:
    cnt = Counter(memoi)
    cnt_v = [ci for ci in list(cnt.values()) if ci > 1]
    temp = fac[n]
    if len(memoi) <= n:
        for cnt_vi in cnt_v:
            temp = (temp*facInv[cnt_vi]) % MOD
        temp = (temp*facInv[n-len(memoi)]) % MOD
    
    ans = (ans+temp) % MOD
        
if m==1 or n==1:
    print(1)
else:
    print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import factorial as fac

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

factor = {}
tmp = 2
while(M // tmp >= 1):
    if(M % tmp != 0):
        if(tmp == 2):
            tmp += 1
        else:
            tmp += 2
        continue

    M = M // tmp
    factor[tmp] = factor.get(tmp, 0) + 1

if(factor == {}):
    print(1)
    sys.exit()

ans = 1
max_a = 7 + 10 ** 9
tt = fac(N - 1)
# print(factor)
for i in factor.values():
    # print(i)
    a = 1
    for j in range(N, N + i):
        a = a * j
    tmp = a // fac(i)
    ans = (ans * tmp) % max_a
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from bisect import bisect_right

# nの逆元のリスト
def inv_mod(n:int, mod:int) -> list:
    inv = [0,1]
    for i in range(2,n+1):
        inv.append(mod - ((mod//i)*inv[mod%i]) % mod)
    return inv
       
# nの階乗のリスト
def fact(n:int, mod:int) -> list:
    fac = [1,1]
    res = 1
    for i in range(2,n+1):
        res = res*i%mod
        fac.append(res)
    return fac

# nの階乗の逆元のリスト
def fact_inv(n:int, inv:list, mod:int) -> list:
    facInv = [1,1]
    for i in range(2,n+1):
        facInv.append(facInv[i-1]*inv[i] % mod)
    return facInv
        

from collections import Counter

n,m = li()

MOD = 10**9+7

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


# Mの素因数リストを作る

def cd(n:int):
    m = 2
    cds = set([n])
    while m*m <= n:
        if n%m == 0:
            cds.add(m)
            cds.add(n//m)
            
        m += 1

    return sorted(list(cds))
    
cds = cd(m)

memo = []

def dfs(m: int, cds: list, res:int,st:list):
    if res == 1:
        memo.append(st)
        
    else:
        idx = bisect_right(cds,st[-1])
        for cdi in cds[:idx]:
            if cdi > st[-1]:
                pass
            else:
                if res%cdi == 0:
                    dfs(m,cds,res//cdi,st+[cdi])
                

# 辞書順にmを作れるオリジナルなセットを作る
for cdi in cds:
    dfs(m,cds,m//cdi,[cdi])


ans = 0
for memoi in memo:
    cnt = Counter(memoi)
    cnt_v = list(cnt.values())
    temp = fac[n]
    if len(memoi) <= n:
        for cnt_vi in cnt_v:
            if cnt_vi > 1:
                temp = (temp*facInv[cnt_vi]) % MOD
        temp = (temp*facInv[n-len(memoi)]) % MOD
    
    ans = (ans+temp) % MOD
        
if m==1 or n==1:
    print(1)
else:
    print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
import math

n, m=map(int, input().split())
t = {}
a = int(math.sqrt(m))

s=0

line = [2, 3] + [i%2*2 + i//2 * 6 + 5 for i in range(a//3)]
while s==0:
    for i in line:
        cnt = 0
        while m%i==0:
            m=m//i
            cnt += 1

        if cnt>0:
            t[i]=cnt

        if m==1:
            s=1
            break

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

out=1
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
 
 
mod = 10**9 + 7


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 *= math.factorial(n+count-1)
    res //=  math.factorial(n - 1)
    res //= math.factorial(count)
    res = res % mod

print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import factorial as fac

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

factor = {}
tmp = 2
while(M // tmp >= 1):
    if(M % tmp != 0):
        if(tmp == 2):
            tmp += 1
        else:
            tmp += 2
        continue

    M = M // tmp
    factor[tmp] = factor.get(tmp, 0) + 1

if(factor == {}):
    print(1)
    sys.exit()

ans = 1
max_a = 7 + 10 ** 9
tt = fac(N - 1)
# print(factor)
for i in factor.values():
    # print(i)
    tmp = fac(N + i - 1) // (fac(i) * tt)
    ans = (ans * tmp) % max_a
print(ans)

Submission status: Time Limit Exceeded

Solution code:
num = (10 ** 9) + 7

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

prime_upper = int(m ** (1/2) + 10)
prime_dict = {}

check = [False] * prime_upper
prime = [2]

while m % 2 == 0:
    m //= 2
    if not 2 in prime_dict.keys():
        prime_dict[2] = 0
    prime_dict[2] += 1

for j in range(2, prime_upper, 2):
    check[j] = True

for i in range(3, prime_upper, 2):
    if not check[i]:
        prime.append(i)
        while m % i == 0:
            m //= i
            if not i in prime_dict.keys():
                prime_dict[i] = 0
            prime_dict[i] += 1

        for j in range(i, prime_upper, i):
            check[j] = True

com2 = [[0] * 50 for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, 50):
        if i == 1:
            com2[i][j] = 1
        elif j == 1:
            com2[i][j] = i
        else:
            com2[i][j] = (com2[i][j - 1] + com2[i - 1][j]) % num
if m != 1:
    ans = n
else:
    ans = 1
for key, value in prime_dict.items():
    ans = (ans * com2[n][value]) % num

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import math
memo={}
def f(x,y,Y):
    if (x,y,Y) in memo:
        return memo[(x,y,Y)]
    ans=0
    if x==0:
        memo[(x,y,Y)]=1
        return 1
    for i in range(y,Y):
        tmp=f(x-1,i,Y)
        memo[(x-1,i,Y)] = tmp
        ans+=tmp
    memo[(x,y,Y)] = ans
    return ans
n,m=map(int,input().split())
s=2
d=[]
count=0
while s<=m:
    if m%s==0:
        m//=s
        count+=1
    else:
        if count:
            d.append(count)
        count=0
        s+=1
d.append(count)
ans=1
d=sorted(d)[::-1]
for x in d:
    ans = (ans*f(x,0,n))%(10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from bisect import bisect_right

# nの逆元のリスト
def inv_mod(n:int, mod:int) -> list:
    inv = [0,1]
    for i in range(2,n+1):
        inv.append(mod - ((mod//i)*inv[mod%i]) % mod)
    return inv
       
# nの階乗のリスト
def fact(n:int, mod:int) -> list:
    fac = [1,1]
    res = 1
    for i in range(2,n+1):
        res = res*i%mod
        fac.append(res)
    return fac

# nの階乗の逆元のリスト
def fact_inv(n:int, inv:list, mod:int) -> list:
    facInv = [1,1]
    for i in range(2,n+1):
        facInv.append(facInv[i-1]*inv[i] % mod)
    return facInv
        

from collections import Counter

n,m = li()

MOD = 10**9+7

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


# Mの素因数リストを作る

def cd(n:int):
    m = 2
    cds = set([n])
    while m*m <= n:
        if n%m == 0:
            cds.add(m)
            cds.add(n//m)
            
        m += 1

    return sorted(list(cds))
    
cds = cd(m)

memo = []

def dfs(m: int, cds: list, res:int,st:list):
    if res == 1:
        memo.append(st)
        
    else:
        idx = bisect_right(cds,st[-1])
        for cdi in cds[:idx]:
            if cdi > st[-1]:
                pass
            else:
                if res%cdi == 0:
                    dfs(m,cds,res//cdi,st+[cdi])
                

# 辞書順にmを作れるオリジナルなセットを作る
for cdi in cds:
    dfs(m,cds,m//cdi,[cdi])

ans = 0
for memoi in memo:
    cnt = Counter(memoi)
    cnt_v = list(cnt.values())
    temp = fac[n]
    if len(memoi) <= n:
        for cnt_vi in cnt_v:
            temp = (temp*facInv[cnt_vi]) % MOD
        temp = (temp*facInv[n-len(memoi)]) % MOD
    
    ans = (ans+temp) % MOD
        
if m==1 or n==1:
    print(1)
else:
    print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

divisors = {}
def findDivisors(M):
    if M in divisors:
        return divisors[M]
    else:
        divisors[M] = [i for i in range(1, M + 1) if M % i == 0]
        return divisors[M]

def f(N, M):
    if N == 2:
        return len(findDivisors(int(M)))
    else:
        return sum([f(N-1, M / i) for i in findDivisors(int(M))])

def main():
    N, M = map(int, input().split())
    print(f(N, M) % (10 ** 9 + 7))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import random

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


mod = 10**9 + 7

def is_prime(x):
    if x < 2: return False # 2未満に素数はない
    if x == 2 or x == 3 or x == 5: return True # 2,3,5は素数
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0: return False # 2,3,5の倍数は合成数

    # ためし割り: 疑似素数(2でも3でも5でも割り切れない数字)で次々に割っていく
    prime = 7
    step = 4
    while prime <= math.sqrt(x):
        if x % prime == 0: return False

        prime += step
        step = 6 - step

    return True


def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  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):
  """a^b mod 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

facts = factorize(M)
# print(facts)

ans = 1

if is_prime(M):
    ans = N
else:
    for fact in facts:
        a = fact[1]
        ans *= comb(a+N-1, N-1, mod)
        ans %= 10**9 + 7

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from math import factorial
Q = 10**9+7
def primes(n):
    primfac = [0]
    d = 2
    while d*d <= n:
        while n%d == 0:
            primfac[-1] += 1
            n //= d
        d += 1
        if primfac[-1] != 0:
            primfac.append(0)
    if n > 1:
        if primfac[-1] == 0:
            primfac[-1] += 1
        else:
            primfac.append(1)
    return primfac
def combination(a,b):
    return ( (factorial(a)//factorial(b))//factorial(a-b))%Q
N, M = map( int, input().split())
C = primes(M)
ans = 1
if N == 1:
    print(1)
else:
    for x in C:
        ans = (ans * combination(x+N-1,N-1))%Q
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


# nの逆元のリスト
def inv_mod(n:int, mod:int) -> list:
    inv = [0,1]
    for i in range(2,n+1):
        inv.append(mod - ((mod//i)*inv[mod%i]) % mod)
    return inv
       
# nの階乗のリスト
def fact(n:int, mod:int) -> list:
    fac = [1,1]
    res = 1
    for i in range(2,n+1):
        res = res*i%mod
        fac.append(res)
    return fac

# nの階乗の逆元のリスト
def fact_inv(n:int, inv:list, mod:int) -> list:
    facInv = [1,1]
    for i in range(2,n+1):
        facInv.append(facInv[i-1]*inv[i] % mod)
    return facInv
        

from collections import Counter

n,m = li()

MOD = 10**9+7

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


# Mの素因数リストを作る

def cd(n:int):
    m = 2
    cds = set([n])
    while m*m <= n:
        if n%m == 0:
            cds.add(m)
            cds.add(n//m)
            
        m += 1

    return sorted(list(cds))
    
cds = cd(m)

memo = []

def dfs(m: int, cds: list, res:int,st:list):
    if res == 1:
        memo.append(st)
        
    else:
        for cdi in cds:
            if cdi > st[-1]:
                pass
            else:
                if res%cdi == 0:
                    dfs(m,cds,res//cdi,st+[cdi])
                

# 辞書順にmを作れるオリジナルなセットを作る
for cdi in cds:
    dfs(m,cds,m//cdi,[cdi])

ans = 0
for memoi in memo:
    cnt = Counter(memoi)
    cnt_v = list(cnt.values())
    temp = fac[n]
    if len(memoi) <= n:
        for cnt_vi in cnt_v:
            temp = (temp*facInv[cnt_vi]) % MOD
        temp = (temp*facInv[n-len(memoi)]) % MOD
    
    ans = (ans+temp) % MOD
        
if m==1 or n==1:
    print(1)
else:
    print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
soi = []
ans = 1
for i in range(2, m):
    if m == 1:
        break
    elif m % i == 0:
        t = 0
        while True:
            if m % i == 0:
                m = m // i
                t += 1
            else:
                break
        soi.append(t)
for i in soi:
    for j in range(min(i, n-1)):
        ans = (ans * (i + n - 1 - j) // (j + 1))
    ans = ans % (10 ** 9 + 7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

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

def prime_factors(n):
    i = 2
    factors = {}
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            if i in list(factors):
                factors[i]+=1
            else:
                factors[i]=1
    if n > 1:
        if n in list(factors):
            factors[n]+=1
        else:
            factors[n]=1
    return factors


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

mod=1000000007

dic=prime_factors(M)
ans=1
for i in list(dic):
    ans*=combinations_count(N+dic[i]-1,N-1)%mod

print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import math
import collections
def trial_division_sqrt(n):

    prime_count = collections.Counter()

    for i in range(2, int(math.sqrt(n)) + 2):
        while n % i == 0:
            n /= i
            prime_count[i] += 1
    if n > 1:
        prime_count[n] += 1

    return prime_count
def pc(n, r):
    return math.factorial(n) // (math.factorial(n - r)  * math.factorial(r))
s=0
x,N = map(int,input().split())

li = trial_division_sqrt(N)
li = li.most_common()
ans = 1
for i in range(0, len(li)):
    ans *= pc(li[i][1] + x-1, x-1)
print(ans % (pow(10, 9)+7))

Submission status: Time Limit Exceeded

Solution code:
import math

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

def prime_factors(n):
    i = 2
    factors = {}
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            if i in list(factors):
                factors[i]+=1
            else:
                factors[i]=1
    if n > 1:
        if n in list(factors):
            factors[n]+=1
        else:
            factors[n]=1
    return factors


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

mod=1000000007

dic=prime_factors(M)
ans=1
for i in list(dic):
    ans*=combinations_count(N+dic[i]-1,N-1)

print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
M = 10 ** 9 + 7

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

    print(solve(m, n))

def solve(m, n):
    prev = dict()

    fs = list(factors(m))
    for f in fs:
        prev[f] = 1

    for _ in range(n - 1):
        row = dict()
        for f in fs:
            s = 0
            for g in factors(f):
                s = (s + prev[f // g]) % M
            row[f] = s
        prev = row

    return prev[m]

def factors(n):
    import itertools

    tail = []
    for i in itertools.count(1):
        if i * i > n:
            break

        m, r = divmod(n, i)
        if r == 0:
            yield i
            if m != i:
                tail.append(m)
    
    for i in tail[::-1]:
        yield i

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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


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 table

pr = prime_decomposition(M)
di = defaultdict(int)
for p in pr:
    di[p] += 1
def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y


# mを法とするaの乗法的逆元
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def combination(n, mod):
    lst = [1]
    for i in range(1, n+1):
        lst.append(lst[-1] * (n+1-i) % mod * modinv(i, mod) % mod)
    return lst
mod = 10**9+7
ans = 1
for k, v in di.items():
    ans *= combination(v+N-1, mod)[N-1]
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np

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

def soin(a):
    fa = []
    i = 2
    d = a
    last = 1
    while d>1:
        if d % i == 0:
            if last == i:
                fa[-1][1]=fa[-1][1]+1
            else:
                fa.append([i,1])
            d=d//i
            last = i
        else:
            i += 1
    return(fa)

#print(soin(n))
q = soin(m)
answer = 1

for i in q:
#    print(i,i[1])
    r = i[1]
    a = 1
    for j in range(n,n+r):
        a = a * j
    for j in range(r):
        a = a // (j+1)
    answer = answer * a % (10**9+7)

print(answer)

Submission status: Time Limit Exceeded

Solution code:
import math
import copy

n, m=map(int, input().split())
t = {}
a = int(math.sqrt(m))

s=0

while s==0:
    for i in range(2, a+2):
#         print(i, m)
        cnt = 0
        while m%i==0:
            m=m//i
            cnt += 1

        if cnt>0:
                t[i]=cnt

        if m==1:
            s=1
            break

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from math import factorial
Q = 10**9+7
def primes(n):
    primfac = []
    d = 2
    while d*d <= n:
        while (n % d) == 0:
            primfac.append(d)  # supposing you want multiple factors repeated
            n //= d
        d += 1
    if n > 1:
       primfac.append(n)
    return primfac

def combination(a,b):
    return ( (factorial(a)//factorial(b))//factorial(a-b))%Q
N, M = map( int, input().split())
C = Counter( primes(M))
ans = 1
if N == 1:
    print(1)
else:
    for x in C:
        ans = (ans * combination(C[x]+N-1,N-1))%Q
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import random

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

mod = 10**9 + 7


def comb(n,k,p):
  """power_funcを用いて(nCk) mod p を求める"""
  from math import factorial
  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):
  """a^b mod 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

facts = factorize(M)
# print(facts)

ans = 1

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
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**5+1000
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())
mb=[]
while m>1:
    for i in range(2,m+1):
        if m%i==0:
            mb.append(i)
            m//=i
            break

mb2=Counter(mb)
    
mblist=list()
for i in mb2:
    a = cmb(mb2[i]+n-1,mb2[i],mod)
    mblist.append(a)
ans=1
for i in mblist:
    ans=(ans*i)%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

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


ans = 1

if m != 1:
    factorization = {}
    while True:
        for i in range (2, m//2 + 1):
            if m % i == 0:
                if i in factorization:
                    factorization[i] += 1
                else:
                    factorization[i] = 1
                m = m // i
                break
        else:
            if m in factorization:
                    factorization[m] += 1
            else:
                factorization[m] = 1
            break


    for i in factorization.keys():
        k = factorization[i]

        num = 1
        for i in range(k):
            num *= (n+k-1-i)
        num //= factorial(k)
        ans *= num % (10**9+7)
        ans = ans % (10**9+7)



print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

nm = input().split()
n = int(nm[0])
m = int(nm[1])

f = []

i = 2
j = 0
while (m > 1) and i<=m:
    while m%i == 0:
        m /= i
        j += 1
    if j >= 1:
        f.append(j)
    i += 1
    j = 0

        
ans = 1

for k in f:
    if k > 0:
        ans *= factorial(n+k-1) // (factorial(k) * factorial(n-1))
    
print(int(ans) % (10**9+7))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np

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

def soin(a):
    fa = []
    i = 2
    d = a
    last = 1
    while d>1:
        if d % i == 0:
            if last == i:
                fa[-1][1]=fa[-1][1]+1
            else:
                fa.append([i,1])
            d=d//i
            last = i
        else:
            i += 1
    return(fa)

#print(soin(n))
q = soin(m)
answer = 1

for i in q:
#    print(i,i[1])
    r = i[1]
    answer = answer * (math.factorial(n+r-1)//math.factorial(n-1)//math.factorial(r)) % (10**9+7)

answer = answer % (10**9+7)

print(answer)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np

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

def soin(a):
    fa = []
    i = 2
    d = a
    last = 1
    while d>1:
        if d % i == 0:
            if last == i:
                fa[-1][1]=fa[-1][1]+1
            else:
                fa.append([i,1])
            d=d//i
            last = i
        else:
            i += 1
    return(fa)

#print(soin(n))
q = soin(m)
answer = 1

for i in q:
#    print(i,i[1])
    r = i[1]
    answer = answer * (math.factorial(n+r-1)//math.factorial(n-1)//math.factorial(r))

answer = answer % (10**9+7)

print(answer)