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

fct = [1]
fct2 = [m]

m_sq = int(m**(1/2)) + 10


for i in range(2,m_sq):
    if m%i==0:
        fct.append(i)
        fct2.append(m//i)

fct = list(set(fct+fct2))
fct.sort()

l = len(fct)
d = {f:i for i,f in enumerate(fct)}

dp = [[0 for i in range(l)] for j in range(n)]
dp[0] = [1]*(l)

for i in range(1,n):
    for j in range(l):
        fj = fct[j]
        for k in range(j+1):
            fk = fct[k]
            if fj%fk==0:
                dp[i][j] += dp[i-1][k]
                dp[i][j] %= mod
print(dp[n-1][l-1])

Submission status: Time Limit Exceeded

Solution code:
#imsosorryididntwanttoimplementmodpow
import math
n,m = [int(x) for x in input().split()]

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

i = 2
ans = 1
while (i<=m):
    if m%i==0:
        mult = 0
        while (m%i==0):
            mult += 1
            m //= i
        ans *= comb(n+mult-1,n-1)
    i += 1
if m!=1:
    ans *= comb(n,n-1)

print(ans%int(1e9+7))

Submission status: Time Limit Exceeded

Solution code:
import math

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


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

l = [2]
now = 3

while now ** 2 <= M:
    flag = True
    for i in l:
        if now % i == 0:
            flag = False
            break
    if flag:
        l.append(now)
    now += 2

dic = {}
for i in l:

    while M % i == 0:
        if i not in dic:
            dic[i] = 1
        else:
            dic[i] += 1

        M //= i

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

ans = 1
#print (dic)

for i in dic:
    ans *= nCr(dic[i] + N - 1,dic[i])
    #print (ans)
    ans %= (10 ** 9 + 7)
print (ans % (10**9+7))

Submission status: Time Limit Exceeded

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

fac = [0] * (N + 33)
inv = [0] * (N + 33)
finv = [0] * (N + 33)

fac[0] = fac[1] = 1
inv[1] = 1
finv[0] = finv[1] = 1

for i in range(2, N+33):
  fac[i] = fac[i-1] * i % p
  inv[i] = p - inv[p%i] * (p // i) % p
  finv[i] = finv[i-1] * inv[i] % p

primes = {}
i = 2
while(M > 1):
  if(M % i == 0):
    primes[i] = primes.get(i, 0) + 1
    M //= i
  else:
    i += 2 - (i + 1) % 2
r = 1
for v in primes.values():
  r = r * fac[N+v-1] * finv[N-1] * finv[v] % p
print(r)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def divisors(n):
    S,T=[],[]
    for i in range(1,int(n**.5)+1):
        if n%i==0:
            S.append(i)
            T.append(n//i)
    T.reverse()
    return S+T if S[-1]!=T[0] else S+T[1:]

def resolve():
    n,m=map(int,input().split())
    D=divisors(m)
    dp={d:0 for d in D}
    dp[1]=1
    for _ in range(n):
        ndp={d:0 for d in D}
        for d in D:
            for d1 in D:
                if(m%(d*d1)!=0): continue
                ndp[d*d1]+=dp[d]
                ndp[d*d1]%=MOD
        dp=ndp
    print(ndp[m])
resolve()

Submission status: Time Limit Exceeded

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

    pow_ = [0] * 31
    divisor = 2
    power = 0
    while m % divisor == 0:
        m //= divisor
        power += 1
    if power > 0:
        pow_[power] += 1

    divisor = 3
    while m > 1:
        power = 0
        while m % divisor == 0:
            m //= divisor
            power += 1
        if power > 0:
            pow_[power] += 1
        divisor += 2

    # print(pow_)

    ans = 1
    t = 1
    d = 1
    for power, cnt in enumerate(pow_[1:], 1):
        # 1 <= power <= 30
        t = t * (n - 1 + power) % mod
        d = d * pow(power, mod - 2, mod) % mod
        # print(power, cnt, ans, t, d)
        ans = ans * pow(t * d % mod, cnt, mod) % mod
        # for _ in range(cnt):
        #     ans = ans * t * d % mod
    print(ans)

Submission status: Time Limit Exceeded

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

    pow_ = [0] * 31
    divisor = 2
    power = 0
    while m % divisor == 0:
        m //= divisor
        power += 1
    if power > 0:
        pow_[power] += 1

    divisor = 3
    while m > 1:
        power = 0
        while m % divisor == 0:
            m //= divisor
            power += 1
        if power > 0:
            pow_[power] += 1
        divisor += 2

    # print(pow_)

    ans = 1
    t = 1
    d = 1
    for power, cnt in enumerate(pow_[1:], 1):
        # 1 <= power <= 30
        t = t * (n - 1 + power) % mod
        d = d * pow(power, mod - 2, mod) % mod
        # print(power, cnt, ans, t, d)
        ans = ans * pow(t * d, cnt, mod) % mod
        # for _ in range(cnt):
        #     ans = ans * t * d % mod
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

pow_ = [0] * 31
divisor = 2
power = 0
while m % divisor == 0:
    m //= divisor
    power += 1
if power > 0:
    pow_[power] += 1

divisor = 3
while m > 1:
    power = 0
    while m % divisor == 0:
        m //= divisor
        power += 1
    if power > 0:
        pow_[power] += 1
    divisor += 2

# print(pow_)

ans = 1
t = 1
d = 1
for power, cnt in enumerate(pow_[1:], 1):
    # 1 <= power <= 30
    t = t * (n - 1 + power) % mod
    d = d * pow(power, mod - 2, mod) % mod
    # print(power, cnt, ans, t, d)
    for _ in range(cnt):
        ans = ans * t * d % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# ABC110d
import sys
from collections import Counter
import math
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


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


def combinations_with_replacement_count(n, r):
    return combinations_count(n + r - 1, r)


ans = 1
pr = Counter(prime_factorize(m))
for i in pr.values():
    # print(i)
    t = combinations_count(n + i - 1, i)
    # print(t)
    ans = ans*t % MOD
# print(pr)
# print(len(pr))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from operator import mul

def prime_facts(n):
  facts = {}
  for i in range(2,n+1):
    while n%i==0:
      if i not in facts:facts[i] = 1
      else:facts[i] += 1
        
      n /= i
  return facts

def ncr(n, r):
    r = min(r, n-r)
    numer = reduce(mul, range(n, n-r, -1), 1)
    denom = reduce(mul, range(1, r+1), 1)
    return numer / denom


MOD = 10**9 + 7  
N, M = map(int,input().split())
ans = 1
for fact_num in prime_facts(M).values():
  ans *= ncr(fact_num+N-1,fact_num)%MOD
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import math
N, M = list(map(int, input().split(' ')))
MOD = int(1e9 + 7)
primes = []
if M % 2 == 0:
  primes.append(2)
def is_prime(n):
  for i in range(len(primes)):
    if n % primes[i] == 0:
      return False
  return True
for i in range(3, int(1e5)):
  if is_prime(i):
    primes.append(i)

seeds = []
for p in primes:
  while M % p == 0:
    seeds.append(p)
    M = M // p

def comb(n, k):
  ans = 1
  for i in range(1, k + 1):
    ans = (ans * (n + 1 - i) // i)
  return ans

ans = comb(len(seeds)-1, N-1)
# !!! 24=(2^a1 * 3^b1) * (2^a2 * 3^b2) * ... | sum(a) = 3, sub(b) = 1, len(a) = 4
# aのパターン数は 3,0,0,0 = ooo|||, 2,1,0,0 = oo|o|| なので並び替えのパターン数で
# (sum(a) + 分ける数)! / (sum(a)! * 分ける数!) = (6!/(3!3!)) = 20
# b にも同じことをして 1,0,0,0 = o||| = (1+3)!/(1!*3!) = 4
# 24を4つに分けるパターンは 20 * 4 = 80?

# (a+b)!/(a!b!) = (a+b)Ca = (a+b)Cb

ans = 1
hogehoge = set(seeds)
for i in hogehoge:
  a_ct = seeds.count(i)
  ans = (ans * comb(a_ct + N-1, min(a_ct, N-1))) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
mod = 1000000007
d = 1
divisor = []
while d * d <= m:
    if m % d == 0:
        divisor.append(d)
        if d != m // d:
            divisor.append(m // d)
    d += 1
divisor = sorted(divisor)
l = len(divisor)
matrix = [[0] * l for _ in range(l)]
for i in range(l):
    for j in range(l):
        matrix[i][j] = 1 if divisor[i] % divisor[j] == 0 else 0

dp = [1] * l
t = n - 1
while t > 0:
    if t % 2 == 1:
        newdp = [0] * l
        for i in range(l):
            for j in range(l):
                newdp[i] = (newdp[i] + matrix[i][j] * dp[j]) % mod
        dp = newdp
    newmatrix = [[0] * l for _ in range(l)]
    for i in range(l):
        for j in range(i + 1):
            newmatrix[i][j] = sum(matrix[i][k] * matrix[k][j] for k in range(j, i + 1)) % mod
    matrix = newmatrix
    t //= 2

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
mod = 1000000007
d = 1
divisor = []
while d * d <= m:
    if m % d == 0:
        divisor.append(d)
        if d != m // d:
            divisor.append(m // d)
    d += 1
divisor = sorted(divisor)
l = len(divisor)
matrix = [[0] * l for _ in range(l)]
for i in range(l):
    for j in range(l):
        matrix[i][j] = 1 if divisor[i] % divisor[j] == 0 else 0

dp = [1] * l
t = n - 1
while t > 0:
    if t % 2 == 1:
        newdp = [0] * l
        for i in range(l):
            for j in range(l):
                newdp[i] = (newdp[i] + matrix[i][j] * dp[j]) % mod
        dp = newdp
    newmatrix = [[0] * l for _ in range(l)]
    for i in range(l):
        for j in range(l):
            newmatrix[i][j] = sum(matrix[i][k] * matrix[k][j] for k in range(l)) % mod
    matrix = newmatrix
    t //= 2

print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

def getlist():
	return list(map(int, input().split()))

const = 10 ** 9 + 7
MAX = 10 ** 5 + 50

#エラトステネス
L = [1 for i in range(100101)]
L[0] = 0
L[1] = 0
plist = []
for i in range(100101):
	if L[i] == 1:
		plist.append(i)
		c = 2
		while True:
			if i * c <= 100100:
				L[i * c] = 0
				c += 1
			else:
				break

#組み合わせ、逆元前計算
fac = [0] * (MAX)
inv = [0] * (MAX)
finv = [0] * (MAX)
fac[0], fac[1] = 1, 1
inv[1] = 1
finv[0], finv[1] = 1, 1

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

#受け取り、処理
N, M = getlist()
if M == 1:
	print(1)
else:
	D = defaultdict(int)
	while M != 1:
		for i in plist:
			if M % i == 0:
				D[i] += 1
				M = M // i
				break

	data = []
	for i in D:
		data.append(D[i])

	#計算
	ans = 1
	for i in data:
		ans *= fac[i + N - 1] * finv[i] * finv[N - 1]
		ans %= const
	print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

def getlist():
	return list(map(int, input().split()))

const = 10 ** 9 + 7
MAX = 10 ** 5 + 50

#エラトステネス
L = [1 for i in range(100001)]
L[0] = 0
L[1] = 0
plist = []
for i in range(100001):
	if L[i] == 1:
		plist.append(i)
		c = 2
		while True:
			if i * c <= 100000:
				L[i * c] = 0
				c += 1
			else:
				break

#組み合わせ、逆元前計算
fac = [0] * (MAX)
inv = [0] * (MAX)
finv = [0] * (MAX)
fac[0], fac[1] = 1, 1
inv[1] = 1
finv[0], finv[1] = 1, 1

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

#受け取り、処理
N, M = getlist()
if M == 1:
	print(1)
else:
	D = defaultdict(int)
	while M != 1:
		for i in plist:
			if M % i == 0:
				D[i] += 1
				M = M // i
				break

	data = []
	for i in D:
		data.append(D[i])

	#計算
	ans = 1
	for i in data:
		ans *= fac[i + N - 1] * finv[i] * finv[N - 1]
		ans %= const
	print(ans)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import math

def main():
    N,M = map(int,input().split())
    div_list = []
    d = 2
    ans = 1
    while M != 1:
        count = 0
        while M%d == 0:
            count += 1
            M //= d
        div_list.append(count)
        d += 1
    for i in div_list:
        a = math.factorial(i+N-1)
        b = math.factorial(i)
        c = math.factorial(N-1)
        ans *= (a//(b*c))%(10**9+7)
    print(ans%(10**9+7))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

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



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


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

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

ans = anst
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

d = defaultdict(int)
for i in range(2, M+1):
    while M % i == 0:
        d[i] += 1
        M //= i
    if M == 1:
        break


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 = 100100
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)


ans = 1
for v in d.values():
    # print(v, cmb(v+N, N, mod))
    ans *= cmb(v+N-1, N-1, mod)

print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
#coding utf-8
import math
N,M=map(int,input().split())

def soinsu(m):
  fact =[]
  i = 2
  while i*i<=m:
    if m%i==0:
      fact.append(i)
      m //=i
    else:
      i +=1
  if m>1:
    fact.append(m)
  return fact

fact=soinsu(M)
counting=[]
for i in fact:
  counting.append(fact.count(i))
  del fact[:fact.count(i)-1]
  if fact==[]:
    break

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

ans = 1
for i in counting:
  ans *=combi(i+N-1,N-1)

print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import copy
import math
import collections

inf = (10 ** 9) + 7
n, m = map(int, input().split())
prime_dict = {}
m_copy = copy.deepcopy(m)
while (m_copy % 2 == 0):
    m_copy = int(m_copy // 2)
    if 2 not in prime_dict.keys():
        prime_dict[2] = 1
    else:
        prime_dict[2] += 1
for i in range(3, int(math.sqrt(m)) + 1, 2):
    while (m_copy % i == 0):
        m_copy = int(m_copy // i)
        if i not in prime_dict.keys():
            prime_dict[i] = 1
        else:
            prime_dict[i] += 1
if m_copy != 1:
    if m_copy not in prime_dict.keys():
        prime_dict[m_copy] = 1
    else:
        prime_dict[m_copy] += 1
b = list(prime_dict.values())
ans = 1
for bb in b:
    ans *= math.factorial(bb + n - 1) % inf
    ans *= pow(math.factorial(bb), inf - 2, inf)
    ans *= pow(math.factorial(n - 1), inf - 2, inf)
    ans = ans % inf
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
import math
import collections

inf = (10 ** 9) + 7
n, m = map(int, input().split())
prime_list = []
m_copy = copy.deepcopy(m)
while (m_copy % 2 == 0):
    m_copy = int(m_copy // 2)
    prime_list.append(2)
for i in range(3, int(math.sqrt(m)) + 1, 2):
    while (m_copy % i == 0):
        m_copy = int(m_copy // i)
        prime_list.append(i)
if m_copy != 1:
    prime_list.append(m_copy)
k = collections.Counter(prime_list)
b = list(k.values())
ans = 1
for bb in b:
    ans *= math.factorial(bb + n - 1) % inf
    ans *= pow(math.factorial(bb), inf - 2, inf)
    ans *= pow(math.factorial(n - 1), inf - 2, inf)
    ans = ans % inf
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
inf = (10 ** 9) + 7
n, m = map(int, input().split())
prime_list = []
m_copy = copy.deepcopy(m)
while (m_copy % 2 == 0):
    m_copy = int(m_copy // 2)
    prime_list.append(2)
for i in range(3, int(m // 2) + 1, 2):
    while (m_copy % i == 0):
        m_copy = int(m_copy // i)
        prime_list.append(i)
import collections
k = collections.Counter(prime_list)
b = list(k.values())
import math
ans = 1
for bb in b:
    ans *= math.factorial(bb + n - 1) % inf
    ans *= pow(math.factorial(bb), inf - 2, inf)
    ans *= pow(math.factorial(n - 1), inf - 2, inf)
    ans = ans % inf
print(ans)

Submission status: Time Limit Exceeded

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


def trial_division(n):
    l = []
    f = 2
    while n > 1:
        if n % f == 0:
            l.append(f)
            n /= f
        else:
            f += 1
    return l


def combinations_count(n, r):
    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())

c = collections.Counter(trial_division(M))
a = 1
for i in c.values():
    a *= combinations_count(i + N - 1, i)

print(a % (10**9 + 7))

Submission status: Time Limit Exceeded

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


def trial_division(n):
    l = []
    f = 2
    while n > 1:
        if (n % f == 0):
            l.append(f)
            n /= f
        else:
            f += 1
    return l


def combinations_count(n, r):
    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())

c = collections.Counter(trial_division(M))
a = 1
for i in c.values():
    a *= combinations_count(i + N - 1, i)

print(a % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
import collections
import math


def trial_division(n):
    l = []
    f = 2
    while n > 1:
        if (n % f == 0):
            l.append(f)
            n /= f
        else:
            f += 1
    return l


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


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

c = collections.Counter(trial_division(M))
a = 1
for i in c.values():
    a *= combinations_count(i + N - 1, i)

print(a % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce


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


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

    m0 = m
    primes = {}
    p = 2
    # prime factorization
    while m0 > 1:
        if m0 % p == 0:
            m0 /= p
            if p in primes:
                primes[p] += 1
            else:
                primes[p] = 1
        else:
            p += 1

    ans = 1
    for _, v in primes.items():
        ans *= cmb(n - 1 + v, v)
        ans %= MOD
    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
from scipy.misc import comb


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

    m0 = m
    primes = {}
    p = 2
    # prime factorization
    while m0 > 1:
        if m0 % p == 0:
            m0 /= p
            if p in primes:
                primes[p] += 1
            else:
                primes[p] = 1
        else:
            p += 1

    ans = 1
    for _, v in primes.items():
        ans *= comb(n - 1 + v, v, exact=True)
        ans %= MOD
    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
mod = 1000000007


def calc(a, b):
    am = 1
    ad = 1
    for i in range(b):
        am *= (a - i) % mod
        ad *= (i + 1) % mod
    return am * modpow(ad, mod - 2) % mod


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


def main():
    N, M = map(int, input().split())
    res = M
    ans = 1
    i = 2
    while res >= i * i:
        if res % i == 0:
            c = 0
            while res % i == 0:
                c += 1
                res //= i
            ans *= calc(N + c - 1, N - 1) % mod
        i += 1
    if res != 1:
        ans *= calc(N, N - 1) % mod
    print(ans)


main()

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7

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

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

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

factors = defaultdict(int)
i = 2
while M > 1:
    while M % i == 0:
        M //= i
        factors[i] += 1
    i += 1

ans = 1
for n in factors.values():
    ans *= nHr(N, n)
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from math import factorial

MOD = 10 ** 9 + 7

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

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

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

factors = defaultdict(int)
i = 2
while M > 1:
    while M % i == 0:
        M //= i
        factors[i] += 1
    i += 1

ans = 1
for n in factors.values():
    ans *= nHr(N, n)
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections, math, functools, sys

mod = 10 ** 9 + 7
sys.setrecursionlimit(mod)

@functools.lru_cache(maxsize=None)
def c(x, y):
    if y == 0 or x == y:
        return 1
    else:
        return (c(x - 1, y - 1) + c(x - 1, y)) % mod

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

d = collections.defaultdict(int)
t = m
for x in range(2, math.ceil(math.sqrt(t)) + 1):
    while t % x == 0:
        d[x] += 1
        t //= x

if t > 1:
    d[t] += 1

ans = 1
for v in d.values():
    ans *= c(n + v - 1, v)
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#ABC110 D

import math
from collections import Counter
N,M = map(int,input().split())
mod = 10**9 + 7

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

def fast(x,n):
    if n == 0:
        return 1
    elif n % 2 == 0:
        return fast(x**2 % mod,n//2) % mod
    elif n % 2:
        return x*fast(x**2 % mod,n//2) % mod

cnt = list(Counter(factorize(M)).items())
ans = 1
for i,j in cnt:
    ans *= math.factorial(j+N-1)
    ans %= mod
    ans *= fast(math.factorial(j),mod-2)
    ans %= mod
    ans *= fast(math.factorial(N-1),mod-2)
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
INF = 10**9+7
inv = {}
inv[0] = 1
inv[1] = 1
def p(x):
    if x in inv:
        return inv[x]
    else:
        inv[x] = ((-1)* p(INF%x) * (INF//x))% INF
        return inv[x]
# n H y
memo = [0 for i in range(m+1)]
def f(y):
    def g(v):
        if v == 0:
            return 1
        elif v == 1:
            return n
        elif memo[v] != 0:
            return memo[v]
        else:
            memo[v] = ((n+v-1)*g(v-1)*p(v))%INF
            return memo[v]
    return g(y)
# M を素因数分解
def h(x):
    t = x
    d = {}
    for i in range(2,x):
        if i*i > x:
            break
        if t % i != 0:
            continue
        if t % i == 0:
            ind = 0
            while t % i == 0:
                t = t // i
                ind += 1
            d[i] = ind
    if t != 1:
        d[x] = 1
    return d

res = 1
for i in h(m):
    res = (res *  f(h(m)[i])) % INF

print(res)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
INF = 10**9+7
# x個の区別できる箱にy個の区別できない球を入れる場合の数
memo = [[0 for i in range(m+1)] for j in range(n+1)]
def f(x,y):
    def g(u,v):
        if u == 0:
            return 1
        elif v == 0:
            return 1
        elif v == 1:
            return u
        elif u == 1:
            return 1
        elif memo[u][v] != 0:
            return memo[u][v]
        else:
            memo[u][v] = sum([g(u-1,i) for i in range(v+1)])
            return memo[u][v]
    return g(x,y)
# M を素因数分解
def h(x):
    t = x
    d = {}
    for i in range(2,x):
        if i*i > x:
            break
        if t % i != 0:
            continue
        if t % i == 0:
            ind = 0
            while t % i == 0:
                t = t // i
                ind += 1
            d[i] = ind
    if t != 1:
        d[x] = 1
    return d

res = 1
for i in h(m):
    res = (res *  f(n,h(m)[i])) % INF

print(res)

Submission status: Time Limit Exceeded

Solution code:
import math
import os
import sys
from collections import Counter

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = list(map(int, sys.stdin.readline().split()))


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

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


def ncr(n, r, mod=None):
    """
    scipy.misc.comb または scipy.special.comb と同じ
    組み合わせの数 nCr
    :param int n:
    :param int r:
    :param int mod: 3 以上の素数であること
    :rtype: int
    """
    if n < r:
        return 0

    return math.factorial(n) // math.factorial(r) // math.factorial(n - r)


factors = get_factors(M)

ans = 1
for c in Counter(factors).values():
    # N 個の箱から重複ありで c 個選ぶ
    ans = ans * ncr(N + c - 1, c) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
def factorize(m):
    fct = []
    b = 2
    while b * b <= m:
        cnt = 0
        while m % b == 0:
            m //= b
            cnt += 1
        if b > 0:
            fct.append([b, cnt])
        b += 1 
    if m > 1:
        fct.append([m, 1])
    return fct

def comb(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    else:
        return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))

N, M = map(int, input().split())
ans = 1
M_fct = factorize(M)

for mf in M_fct:
    #mf[1]個をN通りに分ける→comb(mf[1]+N-1,mf[1])
    ans *= comb(N + mf[1] - 1, mf[1])
print(ans% (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
import math
import collections
def factorize(m):
    b = 2
    fct = []
    while b * b <= m:
        while m % b == 0:
            m //= b
            fct.append(b)
        b += 1
    if m > 1:
        fct.append(m)
    return fct

def comb(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    else:
        return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))

N, M = map(int, input().split())
ans = 1
M_fact = factorize(M)
c = collections.Counter(M_fact)

for ci in c.values():
    #i個をN通りに分ける→i+N-1,i
    ans *= comb(N+ci-1,ci)
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

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

def c(n,m):
    import math
    if n-m<0:
        return 0
    return(math.factorial(n)//math.factorial(n-m)//math.factorial(m))

def factorize(n):
    fct=[]
    b,e=2,0
    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

l=factorize(m)
mod=10**9+7
ans=1
for i,j in l:
    ans*=c(j+n-1,j)
    ans=ans%mod

print(ans)

Submission status: Time Limit Exceeded

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

def factoring(k): #kを因数分解し、素因数とその個数を辞書に入れて返す。
    dic = dict()
    n = int(math.sqrt(k))+2
    for i in range(2, n):
        count = 0
        while k%i == 0:
            count += 1
            k = k//i
        if count != 0:
            dic[i] = count
    if k != 1:
        dic[k] = 1
    return dic

def conbination(n, r): #nCrを求める
    # nCr = n! //(r! * (n-r)!)
    import math
    return (math.factorial(n) //(math.factorial(r) * math.factorial(n-r)))%MOD
dic = factoring(M)
ans = 1
for i in dic:
    ans = (ans * conbination(dic[i]+N-1, dic[i]))%MOD
print (ans)

Submission status: Time Limit Exceeded

Solution code:
import math
m,n=map(int,input().split())
k=int(math.sqrt(n))
ju=[False for i in range(k+1)]
da=[]
ki=2
co=-1
while ki<k+1:
	if n%ki==0:
		n//=ki
		if ju[ki]:
			da[co]+=1
		else:
			co+=1
			da.append(1)
			ju[ki]=True
	else:
		ki+=1
co+=1
ans=1
for i in range(co):
	si=da[i]
	dp=[[0 for i in range(si+1)] for j in range(m+1)]
	dp[0][0]=1
	for j in range(1,m+1):
		for k in range(si+1):
			for l in range(k+1):
				dp[j][k]=(dp[j-1][l]+dp[j][k])%(1000000007)
	ans=(ans*dp[m][si])%(1000000007)
if n>1:
	ans=((ans*m)%1000000007)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

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

MOD = 10 ** 9 + 7

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

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