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:
N,M=map(int,input().split())
mod=10**9+7

from math import factorial
from collections import Counter

def soinsuu(n):
    list_=[]
    while(n!=1):
        for i in range(2,int(n**0.5)+1):
            if n%i==0:
                list_.append(i)
                n=n//i
                break
        else:
            list_.append(n)
            n=1
    return sorted(list_)

def product(a):
    pro=1
    for b in a:
        pro=pro*b%mod
    return pro

#n!,nPr,nCrの高速計算
def n_func(n,mod=10**9+7):
    ans=1
    for i in range(1,n+1):
        ans=(ans*i)%mod
    return ans
def inv_n(n,mod=10**9+7):
    return pow(n,mod-2,mod)
def nPr(n,r,mod=10**9+7):
    ans=n_func(n-r,mod)
    ans=inv_n(ans,mod)
    return ans*n_func(n,mod)%mod

def dp(cur,init,seq,lest,num):
    if cur==N:
        if lest==0:
            cnt=list(Counter(seq).values())
            bunbo=product(map(factorial,cnt[1:]))
            memo[num]=(memo[num]+nPr(sum(cnt),sum(cnt[1:]),mod)*inv_n(bunbo))%mod
    elif lest==0:
        dp(N,init,seq+[0]*(N-cur),0,num)
    else:
        for i in range(1,lest+1):
            if cur==0:
                dp(cur+1,init,seq+[i],lest-i,num)
            elif i<=seq[-1]:
                dp(cur+1,init,seq+[i],lest-i,num)

p=list(Counter(soinsuu(M)).values())
memo=[0]*len(p)

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

Submission status: Time Limit Exceeded

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

from math import factorial
from collections import Counter

def soinsuu(n):
    list_=[]
    while(n!=1):
        for i in range(2,int(n**0.5)+1):
            if n%i==0:
                list_.append(i)
                n=n//i
                break
        else:
            list_.append(n)
            n=1
    return sorted(list_)

def product(a):
    pro=1
    for b in a:
        pro=pro*b%mod
    return pro

#n!,nPr,nCrの高速計算
def n_func(n,mod=10**9+7):
    ans=1
    for i in range(1,n+1):
        ans=(ans*i)%mod
    return ans
def inv_n(n,mod=10**9+7):
    return pow(n,mod-2,mod)
def nPr(n,r,mod=10**9+7):
    ans=n_func(n-r,mod)
    ans=inv_n(ans,mod)
    return ans*n_func(n,mod)%mod

def dp(cur,init,seq,lest,num):
    if cur==N:
        if lest==0:
            cnt=sorted(list(Counter(seq).values()),reverse=True)
            bunbo=product(map(factorial,cnt[1:]))
            memo[num]=(memo[num]+nPr(sum(cnt),sum(cnt[1:]),mod)*inv_n(bunbo))%mod
    elif lest==0:
        dp(N,init,seq+[0]*(N-cur),0,num)
    else:
        for i in range(1,lest+1):
            if cur==0:
                dp(cur+1,init,seq+[i],lest-i,num)
            elif i<=seq[-1]:
                dp(cur+1,init,seq+[i],lest-i,num)

p=list(Counter(soinsuu(M)).values())
memo=[0]*len(p)

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

Submission status: Time Limit Exceeded

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


def solve(s):
    n, m = map(int, s.split())
    if m == 1:
        return 1
    divisor = []
    for i in range(2, int(m**0.5) + 1):
        if m % i == 0:
            divisor.append(i)
    divisor += [m // d for d in divisor[::-1]] + [m]
    divisor = sorted(list(set(divisor)))

    def search(ded, use, j):
        if ded == 1:
            # print("{} {} {}".format(ded, use, j))
            count = Counter(use)
            base = reduce(mul, range(n - len(use) + 1, n + 1))
            for v in list(count.values()):
                base //= factorial(v)
            # print(base)
            return base
        if len(use) >= n:
            return 0

        tmp = [
            search(ded // d, use + [d], i + j) for i, d in enumerate(divisor[j:]) if ded % d == 0
        ]
        return sum(tmp) if tmp else 0

    return search(m, [], 0) % (10**9 + 7)


print(solve(input()))

Submission status: Time Limit Exceeded

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


def solve(s):
    n, m = map(int, s.split())
    if m == 1:
        return 1
    divisor = []
    for i in range(2, int(m**0.5) + 1):
        if m % i == 0:
            divisor.append(i)
    divisor += [m // d for d in divisor[::-1]] + [m]
    divisor = sorted(list(set(divisor)))
    ld = len(divisor)

    def search(ded, use, j):
        if ded == 1:
            # print("{} {} {}".format(ded, use, j))
            count = Counter(use)
            base = reduce(mul, range(n - len(use) + 1, n + 1))
            for v in list(count.values()):
                base //= factorial(v)
            # print(base)
            return base
        if len(use) >= n:
            return 0

        tmp = [
            search(ded // divisor[i], use + [divisor[i]], i)
            for i in range(j, ld)
            if ded % divisor[i] == 0
        ]
        return sum(tmp) if tmp else 0

    return search(m, [], 0) % (10**9 + 7)


print(solve(input()))

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

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


def comb(n,r):
  if n >= r:
    numer = factorial(n) % mod
    denom_inv = pow(((factorial(r) % mod)* (factorial(n-r) % mod)), mod-2, mod)
    return (numer * denom_inv) % mod
  else:
    return 0


pp = [0]
div = 2
while M > 1:
    if pp[-1] != 0:
        pp.append(0)
    while M % div == 0:
        pp[-1] += 1
        M = M / div
    div += 1

ans = 1
for p in pp:
    ans = (ans * comb(N+p-1, p)) % mod

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N, M = [ int(it) for it in input().split() ]
MOD = 1000000007

import math
sM = int(math.sqrt(M)+1)

p_li = []
m = M
for i in range(sM):
  for j in range(2,sM+1):
    if (m%j)==0:
      p_li.append(j)
      m//=j
      break
  if (m==1):
    break
if (m!=1):
  p_li.append(m)
    
    
import collections
co = collections.Counter(p_li)
vec = co.values()

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
    #[x,y]
    return [w[0],w[1]]

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

s = 1
for v in vec:
  X=N-1+v
  Y=N-1
  if (X-Y<Y):
    Y=X-Y
  ss = 1
  sd = 1
  for i in range(X,X-Y,-1):
    ss = (ss*i)%MOD
  for i in range(Y,0,-1):
    sd = (sd*i)%MOD
  
  ss = (ss*mod_inv(sd,MOD))%MOD
  s = (s*ss)%MOD
print (s%MOD)

Submission status: Time Limit Exceeded

Solution code:
N, M = [ int(it) for it in input().split() ]
MOD = 1000000007

import math
sM = int(math.sqrt(M)+1)

p_li = []
m = M
for i in range(sM):
  for j in range(2,sM+1):
    if (m%j)==0:
      p_li.append(j)
      m//=j
      break
  if (m==1):
    break
if (m!=1):
  p_li.append(m)
    
    
import collections
co = collections.Counter(p_li)
vec = co.values()

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
    #[x,y]
    return [w[0],w[1]]

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

s = 1
for v in vec:
  X=N-1+v
  Y=N-1
  if (X-Y<Y):
    Y=X-Y
  ss = 1
  for i in range(X,X-Y,-1):
    ss = (ss*i)%MOD
  for i in range(Y,0,-1):
    ss = (ss*mod_inv(i,MOD))%MOD
  s = (s*ss)%MOD
print (s%MOD)

Submission status: Time Limit Exceeded

Solution code:
N, M = [ int(it) for it in input().split() ]
MOD = 1000000007

import math
sM = int(math.sqrt(M)+1)

p_li = []
m = M
for i in range(sM):
  for j in range(2,sM+1):
    if (m%j)==0:
      p_li.append(j)
      m//=j
      break
  if (m==1):
    break
if (m!=1):
  p_li.append(m)
    
    
import collections
co = collections.Counter(p_li)
vec = co.values()

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
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m
  
s = 1
for v in vec:
  
  ss = 1
  for i in range(N-1+v,v,-1):
    ss = (ss*i)%MOD
  for i in range(N-1,0,-1):
    ss = (ss*mod_inv(i,MOD))%MOD
  s *= (ss%MOD)
  s = s%MOD
print (s%MOD)

Submission status: Time Limit Exceeded

Solution code:
import collections
import math
n,m=map(int,input().split())
flag=0
P=[]
p=m
while flag==0:
  cur=p
  for i in range(2,int(p**0.5)+1):
    if p%i==0:
      P.append(i)
      p//=i
      break
  if p==cur:
    P.append(p)
    flag=1
c=collections.Counter(P)
Primes=set(P)
def f(i):
  return math.factorial(i)
def fn(i):
  return f(n+i-1)//(f(n-1)*f(i))%(10**9+7)
ans=1
for p in Primes:
  ans*=fn(c[p])
  ans%=(10**9+7)
print(1 if m==1 else ans)

Submission status: Time Limit Exceeded

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

# 素因数分解(小さい方から順に割っていく。sqrt(2)まで)
def factorize(n):
    i = 2
    table = [0]
    cnt= [0]
    while i * i <= n:
        while n % i == 0:
            n /= i
            if table[-1] != i:
                table.append(i)
                cnt.append(0)
            cnt[-1] += 1
        i += 1
    if n > 1:
        table.append(n)
        cnt.append(1)
    return table,cnt

# 組み合わせ
def combination(N,M):
    return factorial(N)//(factorial(M)*factorial(N-M))

fs,ns = factorize(M)
ans = 1
for n in ns[1:]:
    ans *= combination(n+N-1,n)
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

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

# 素因数分解(小さい方から順に割っていく。sqrt(2)まで)
def factorize(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

# 組み合わせ
def combination(N,M):
    return factorial(N)//(factorial(M)*factorial(N-M))

fs = factorize(M)
fset = list(set(fs))
ans = 1
for f in fset:
    cnt = fs.count(f)
    ans *= combination(cnt+N-1,cnt)
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

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

# N,M = 100000,10**9-3
# 素因数分解(小さい方から順に割っていく)
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

# 組み合わせ
def combination(N,M):
    return factorial(N)//(factorial(M)*factorial(N-M))

fs = factorize(M)
fset = list(set(fs))
ans = 1
for f in fset:
    cnt = fs.count(f)
    ans *= combination(cnt+N-1,cnt)
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
import math
sosuu=[]
m0=m
i=2
while i**2<=m:
    if m0%i==0:
        sosuu.append(0)
    while m0%i==0:  
        m0=m0//i
        sosuu[-1]=sosuu[-1]+1
    i=i+1
if m0>1:
    sosuu.append(1)
def c(n,r):
    return math.factorial(n)//(math.factorial(r)*math.factorial(n-r))
answer=1
for i in sosuu:
    a=c(i+n-1,i)
    answer=(answer*a)%(10**9+7)
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)
n,m=map(int,input().split())
divisors=[]
for i in range(1,int(m**0.5)+1):
    if m%i==0:
        divisors.append(i)
        if not i**2==m:
            divisors.append(m//i)
divisors.sort()
dp={}
def f(i,l):
    if (i,l) in dp:
        return dp[(i,l)]
    else:
        if i==n:
            if l==1:
                return 1
            else:
                return 0
        else:
            Sum=0
            for j in divisors:
                if j>l:
                    break
                else:
                    if l%j==0:
                        Sum=Sum+f(i+1,l//j)
            Sum=Sum%(10**9+7)
            dp[(i,l)]=Sum
            return Sum
print(f(0,m))

Submission status: Time Limit Exceeded

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

factor = []
tmp = int(m ** (1/2)) + 1
for i in range(2, tmp):
    while m % i == 0:
        m //= i
        factor.append(i)
if m > 1:
    factor.append(m)
num = list(collections.Counter(factor).most_common())

ans = 1
for x in num:
    ans *= (math.factorial(x[1] + n - 1) // (math.factorial(n - 1) * math.factorial(x[1])) % 1000000007)
    ans %= 1000000007
print(ans)

Submission status: Time Limit Exceeded

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

factor = []
tmp = int(m ** (1/2)) + 1
for i in range(2, tmp):
    while m % i == 0:
        m //= i
        factor.append(i)
if m > 1:
    factor.append(m)
c = collections.Counter(factor)
num = list(c.values())

ans = 1
for i in range(len(num)):
    ans *= (math.factorial(num[i] + n - 1) // (math.factorial(n - 1) * math.factorial(num[i])) % 1000000007)
    ans %= 1000000007
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import collections
import numpy as np
n, m = map(int, input().split())

factor = []
tmp = int(np.sqrt(m)) + 1
for i in range(2, tmp):
    while m % i == 0:
        m //= i
        factor.append(i)
if m > 1:
    factor.append(m)
c = collections.Counter(factor)
num = list(c.values())

ans = 1
for i in range(len(num)):
    ans *= math.factorial(num[i] + n - 1) // (math.factorial(n - 1) * math.factorial(num[i]))
    ans %= 1000000007
print(ans)

Submission status: Time Limit Exceeded

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

fact_dict = {}
i = 2

max_num = 0

while M > 1:
    count = 0
    while M % i == 0:
        M //= i
        count += 1
    if count > 0:
        max_num = max(max_num, count)
        fact_dict[i] = count
    i += 1

def comb(whole, choice):
    choice = min(choice, whole-choice)
    result = 1
    for i in range(whole-choice+1, whole+1):
        result *= i
    for i in range(2, choice+1):
        result //= i
    return result

ans = 1
for _, num in fact_dict.items():
    ans *= comb(N+num-1, N-1)
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
import collections
from operator import mul
from functools import reduce
N, M = map(int, input().split())

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

ps = []
tmp = M
for m in range(2, M+1):
    while tmp % m == 0:
        tmp /= m
        ps.append(m)
    if int(tmp) == 1:
        break
ps = collections.Counter(ps)

ans = 1
mod = 10**9+7
for c in ps.values():
    ans *= cmb(c+N-1, c) % mod
    if ans > mod:
        ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce

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

def Pdeco(m):
    ret=[]
    for i in range(2,M):
        if m<=i:
            if m!=1: ret.append(int(m))
            break
        while m%i==0:
            m=m//i
            ret.append(i)
    return ret


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

L=Pdeco(M)
nums=set(L)

for n in nums:
    p=L.count(n)
    ans=(ans*cmb(N+p-1,N-1))%P

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import itertools
from functools import reduce
from operator import mul
#素因数分解
from collections import Counter


N,M = map(int,input().split())
primes = {}
# primes[1] = 1
tmp = 2
max_count = 0
# while M != 1:
#     if M%tmp==0:
#         M //= tmp
#         if tmp in primes.keys():
#             primes[tmp] += 1
#             max_count = max(max_count,primes[tmp])
#         else:
#             primes[tmp] = 1
#     else:
#         tmp += 1


def factorint(N):
    table = []
    while(N > 1):
        for i in range(2,N+1):
            if N%i == 0:
                while N%i == 0:
                    N = N//i
                    table.append(i)
                break
    table_ = Counter(table)
    return table_

primes = factorint(M)


# def combination(n,r):
#     return math.factorial(n) // (math.factorial(n-r)*math.factorial(r))
def combination(n, r):
    """
    組み合わせの数 nCr
    :param n:
    :param r:
    :return:
    """
    r = min(n - r, r)
    if r == 0:
        return 1
    return reduce(mul, range(n, n - r, -1)) // reduce(mul, range(r, 0, -1))


# print(primes)
ans = 1
for key in primes.keys():
    tmp = combination(primes[key]+N-1,primes[key])

    ans = (ans*tmp)%(10**9+7)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import itertools
from functools import reduce
from operator import mul


N,M = map(int,input().split())
primes = {}
# primes[1] = 1
tmp = 2
max_count = 0
while M != 1:
    if M%tmp==0:
        M //= tmp
        if tmp in primes.keys():
            primes[tmp] += 1
            max_count = max(max_count,primes[tmp])
        else:
            primes[tmp] = 1
    else:
        tmp += 1


# def combination(n,r):
#     return math.factorial(n) // (math.factorial(n-r)*math.factorial(r))
def combination(n, r):
    """
    組み合わせの数 nCr
    :param n:
    :param r:
    :return:
    """
    r = min(n - r, r)
    if r == 0:
        return 1
    return reduce(mul, range(n, n - r, -1)) // reduce(mul, range(r, 0, -1))


# print(primes)
ans = 1
for key in primes.keys():
    tmp = combination(primes[key]+N-1,primes[key])

    ans = (ans*tmp)%(10**9+7)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import itertools


N,M = map(int,input().split())
primes = {}
# primes[1] = 1
tmp = 2
max_count = 0
while M != 1:
    if M%tmp==0:
        M //= tmp
        if tmp in primes.keys():
            primes[tmp] += 1
            max_count = max(max_count,primes[tmp])
        else:
            primes[tmp] = 1
    else:
        tmp += 1


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

# print(primes)
ans = 1
for key in primes.keys():
    tmp = combination(primes[key]+N-1,primes[key])

    ans = (ans*tmp)%(10**9+7)

print(ans)

Submission status: Time Limit Exceeded

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


def get_factors(n):
    """
    素因数分解
    :param int n:
    :type: list of int
    """
    if n <= 1:
        return []

    ret = []
    while n > 2 and n % 2 == 0:
        ret.append(2)
        n //= 2
    i = 3
    while i <= n / 2:
        if n % i == 0:
            ret.append(i)
            n //= i
        else:
            i += 2
    ret.append(n)
    return ret


def comb(n, r):
    """
    組み合わせの数 nCr
    :param n:
    :param r:
    :return:
    """
    r = min(n - r, r)
    if r == 0:
        return 1
    return reduce(mul, range(n, n - r, -1)) // reduce(mul, range(r, 0, -1))


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

# divs = sorted(get_divisors(m))
# # dp[d]: 累積積が d となる数列の数
# dp = {d: 1 for d in divs}
# for _ in range(n - 1):
#     for i in reversed(range(len(divs))):
#         div = divs[i]
#         dp[div] = sum([dp[d] for d in divs if div % d == 0]) % MOD
#     print(dp)
# print(dp)
# おそい


factors = get_factors(m)
counts = Counter(factors)
# k**v を全部かけあわせたやつが m に一致する
# print(functools.reduce(operator.mul, [k ** v for k, v in counts.items()]))

# v 個の k を n 個の数に配分する組み合わせの数
# → v + (n-1) 個のスペースへの v の置き方の組み合わせの数
ans = 1
for k, v in counts.items():
    ans *= comb(v + (n - 1), v)
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

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


def get_divisors(n):
    """
    n の約数をリストで返す
    :param int n:
    :return:
    """
    ret = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            ret.append(i)
            if n // i != i:
                ret.append(n // i)
    return ret


def get_factors(n):
    """
    素因数分解
    :param int n:
    :type: list of int
    """
    ret = []
    i = 2
    while 2 <= i <= n:
        if n % i == 0:
            ret.append(i)
            n //= i
        else:
            i += 1
    return ret


def comb(n, r):
    """
    組み合わせの数 nCr
    :param n:
    :param r:
    :return:
    """
    r = min(n - r, r)
    if r == 0:
        return 1
    return reduce(mul, range(n, n - r, -1)) // reduce(mul, range(r, 0, -1))


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

# divs = sorted(get_divisors(m))
# # dp[d]: 累積積が d となる数列の数
# dp = {d: 1 for d in divs}
# for _ in range(n - 1):
#     for i in reversed(range(len(divs))):
#         div = divs[i]
#         dp[div] = sum([dp[d] for d in divs if div % d == 0]) % MOD
#     print(dp)
# print(dp)
# おそい


factors = get_factors(m)
counts = Counter(factors)
# k**v を全部かけあわせたやつが m に一致する
# print(functools.reduce(operator.mul, [k ** v for k, v in counts.items()]))

# v 個の k を n 個の数に配分する組み合わせの数
# → v + (n-1) 個のスペースへの v の置き方の組み合わせの数
ans = 1
for k, v in counts.items():
    ans *= comb(v + (n - 1), v)
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import Counter

from scipy.misc import comb


def get_divisors(n):
    """
    n の約数をリストで返す
    :param int n:
    :return:
    """
    ret = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            ret.append(i)
            if n // i != i:
                ret.append(n // i)
    return ret


def get_factors(n):
    """
    素因数分解
    :param int n:
    :type: list of int
    """
    ret = []
    i = 2
    while 2 <= i <= n:
        if n % i == 0:
            ret.append(i)
            n //= i
        else:
            i += 1
    return ret


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

# divs = sorted(get_divisors(m))
# # dp[d]: 累積積が d となる数列の数
# dp = {d: 1 for d in divs}
# for _ in range(n - 1):
#     for i in reversed(range(len(divs))):
#         div = divs[i]
#         dp[div] = sum([dp[d] for d in divs if div % d == 0]) % MOD
#     print(dp)
# print(dp)
# おそい


factors = get_factors(m)
counts = Counter(factors)
# k**v を全部かけあわせたやつが m に一致する
# print(functools.reduce(operator.mul, [k ** v for k, v in counts.items()]))

# v 個の k を n 個の数に配分する組み合わせの数
# → v + (n-1) 個のスペースへの v の置き方の組み合わせの数
ans = 1
for k, v in counts.items():
    ans *= comb(v + (n - 1), v, exact=True)
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial as fact
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
num = []
p_flag = [True]*(int(M**0.5)+2)

for i in range(2, int(M**0.5)+2):
    if p_flag:
        for j in range(2*i, int(M**0.5)+2, i):
            p_flag[j] = False

        cnt = 0
        while M % i == 0:
            cnt += 1
            M //= i
        if cnt > 0:
            num.append(cnt)
        if M == 1:
            break
else:
    num.append(1)

ans = 1
for i in num:
    ans = (ans * fact(N-1+i)//(fact(i)*fact(N-1))) % (10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial as fact
import sys
input = sys.stdin.readline

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

for i in range(2, int(M**0.5)+2):
    cnt = 0
    while M % i == 0:
        cnt += 1
        M //= i
    if cnt > 0:
        num.append(cnt)
    if M == 1:
        break
else:
    num.append(1)

ans = 1
for i in num:
    ans = (ans * fact(N-1+i)//(fact(i)*fact(N-1))) % (10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

N,M=map(int,input().split())
dic={}
for i in range(2,int(M**0.5)+1):
    if M%i==0:
        dic.setdefault(i,1)
        M//=i
        while M%i==0:
            dic[i]+=1
            M//=i
    if M==1: break

if M!=1: dic[M]=1


ans=1
for k in dic.keys():
    x=(dic[k]+N-1)
    ans*=math.factorial(dic[k]+N-1)//(math.factorial(dic[k])*math.factorial(N-1))

print(ans%1000000007)

Submission status: Time Limit Exceeded

Solution code:
inpl = lambda: list(map(int,input().split()))
MOD = 10**9 + 7
N, M = inpl()
 
def factorize(n):
  prime_list = []
  factorize_list = []
  i = 2
  while i <= n:
    for p in prime_list:
      if i % p == 0:
        break
    else:
      prime_list.append(i)
      k = 0
      while n % i == 0:
        n //= i
        k += 1
      factorize_list.append(k)
    i += 1
  return(factorize_list)

def H(n,k):
  h = 1
  L = n + k - 1
  k = min(n-1,k)
  for j in range(k):
    h *= L-j
  for j in range(k):
    h //= j+1
  return h

ans = 1
for k in factorize(M):
  ans *= H(N,k) % MOD
  ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial as fac
from collections import defaultdict as ddict
n,m = map(int,input().split())
d = ddict(int)
ans = 1
mod = 10**9+7
def cc(n,r):
  return fac(n)//fac(r)//fac(n-r)
for i in range(2,int(m**.5)+1):
  while m % i == 0:
    d[i] += 1
    m //= i
if m > 1:
  d[m] += 1
for x in d:
  ans = ans * cc(d[x]+n-1,d[x])%mod
print(ans)

Submission status: Time Limit Exceeded

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

def prime(n):#素数かどうか＿素数なら1、そうでないなら0
    for i in range(2,n):
        if n%i==0:
            return 0
    return 1

#def prime_l(n):
#    for i in range(2,n+1):
#        if prime(i)==1:
#            yield i
def prime_l(n):#n以下の素数のリスト
    l=[1 for i in range(2,n+1)]#2からnの、n-1個 インデは-2
    for i in range(n-1):#0からn-2 上記−２=インデ
        if prime(i+2):
            for j in range(2,n//(i+2)+1):#何倍のが0になるか
                l[(i+2)*j-2]=0
    return l



def modpow(a,n,p):#a^n mod p
    res=1
    while n>0:
        if n&1:#１とのビット論理積が１、つまり奇数
            res=res*a%p
        a=a*a%p
        n>>=1
        #ビットの右シフト_2進数表記のnを小数点を固定して右に１桁ずらす_１桁小さくなる
    return res

if m==1:
    print(1)
else:
    #l=[i+2 for i in prime_l(int(1e9))]
    l=prime_l(m)
    #ll=next(l)
    i=0
    d={}
    while m!=1:
        if m%(i+2)==0:
            d[i+2]=1
            m/=i+2
            while m%(i+2)==0:
                d[i+2]+=1
                m/=i+2
        #ll=next(l)
        i+=1
        while l[i]==0:
            i+=1
    #s_k=0
    #for i in d.values():
    #    s_k+=i
    #print(d.values())
    mod=int(1e9+7)
    n_fac=1
    fac_l=[1]#0!
    d_max=max(d.values())
    #for i in range(n+d_max-1):# 1!,2!,,,,(n+d_max-1)!
    #    n_fac*=i+1
    for i in range(n+d_max-1):# 0!,1!,2!,,,,(n+d_max-1)!
        n_fac*=i+1
        n_fac=n_fac%mod
        fac_l.append(n_fac)

    fac_1_l=[]
    for i in range(n+d_max-1):
        fac_1_l.append(modpow(fac_l[i],mod-2,mod))
    w=1
    for dv in d.values():
        w*=fac_l[n+dv-1]
        w=w%mod
        #n_n_fac=fac_l[n-dv]
        #div=int((fac_l[n-1-1]*fac_l[dv-1])%(1e9+7))
        #print(div)
        #if div>w:
        #    w+=1e9+7
        #w=int(w/div)
        w=w*fac_1_l[n-1]%mod
        w=w*fac_1_l[dv]%mod
    print(w)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
from math import factorial    
def comb(a, b):
    ret = factorial(a) // (factorial(a-b)*factorial(b))
    return ret % MOD

if __name__ == '__main__':
    N,M = map(int, input().split())
    ans = 1
    
    #  素因数分解
    i=2
    nokori = M
    while i*i <= nokori:
        if nokori%i==0:
            cnt = 0
            while nokori%i==0:
                cnt += 1
                nokori //= i
            ans *= comb(N+cnt-1, N-1)
            ans %= MOD
        i += 1
            
    if nokori != 1:
        ans *= comb(N+1-1, N-1)
        ans %= MOD
        
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
import math
n, m = [int(item) for item in input().split()]

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[int(n)] += 1
 
    return prime_count

cnt = trial_division_sqrt(m)

ans = 1
for item in cnt:
  ans *= int(math.factorial(n + cnt[item] - 1) // int(math.factorial(cnt[item]) * math.factorial(n-1)))
  ans = int(ans) % (1000000000 + 7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
import math
n, m = [int(item) for item in 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(int(n))
  return collections.Counter(table)

cnt = prime_decomposition(m)

ans = 1
for item in cnt:
  ans *= int(math.factorial(n + cnt[item] - 1) // int(math.factorial(cnt[item]) * math.factorial(n-1)))
  ans = int(ans) % (1000000000 + 7)
print(ans)