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 math import factorial

iN,iM = [int(x) for x in input().split()]
iD = 10**9 +7 #法

def fPrimeCounter(iM):
    iS = int(iM ** 0.5) + 1
    aRet = []
    for i in range(2,iS + 1):
        iCounter = 0
        while iM % i == 0:
            iM = iM / i
            iCounter += 1
        if 0 < iCounter : aRet.append(iCounter)
        if iM == 1 : break
    if 1 < iM  : aRet.append(1)
    return aRet

aP = fPrimeCounter(iM)
iRet = 1
for i in aP:
    iRet *= (factorial(i+iN-1)  // (factorial(iN-1) * factorial(i)) )% iD
iRet %= iD
print(iRet)

Submission status: Time Limit Exceeded

Solution code:
iN,iM = [int(x) for x in input().split()]
iD = 10**9 +7 #法

def fPrimeCounter(iM):
    i = 2
    iS = int(iM ** 0.5) + 1
    aRet = []
    while i < iS or iM != 1:
        iCounter = 0
        while iM % i == 0:
            iM = iM // i
            iCounter += 1
        if 0 < iCounter : aRet.append(iCounter)
        i += 1

    return aRet

#二分累乗法 iDを法として
def fBiPow(iX,iN,iD):
    iY = 1
    while iN > 0:
        if iN % 2 == 0:
            iX = iX * iX % iD
            iN = iN // 2
        else:
            iY = iX * iY % iD
            iN = iN - 1
    return iY

aP = fPrimeCounter(iM)
if aP == [] :
    print (1)
else:
    iMax = max(aP) + iN - 1
    aM = [1] * (iMax + 1)
    #階乗 iD を法とした
    for i in range(1,iMax + 1):
        aM[i] = aM[i-1] * i  % iD
    aInvM = [1]* (iMax + 1)
    aInvM[iMax] = fBiPow(aM[iMax],iD-2,iD)
    #階乗の逆元 iD を法とした
    for i in range(iMax,0,-1):
        aInvM[i-1] = aInvM[i]*i % iD

    iRet = 1
    for i in aP:
        # i + iN -1  C  iN -1
        iRet *= aM[i+iN-1] * aInvM[iN-1] * aInvM[i] % iD
    iRet %= iD
    print(iRet)

Submission status: Time Limit Exceeded

Solution code:
iN,iM = [int(x) for x in input().split()]
iD = 10**9 +7 #法

def fPrimeCounter(iM):
    i = 2
    iS = int(iM ** 0.5) + 1
    aRet = []
    while i < iS or i <= iM  :
        iCounter = 0
        while iM % i == 0:
            iM = iM // i
            iCounter += 1
        if 0 < iCounter : aRet.append(iCounter)
        i += 1
    return aRet

#ABC042Dの流用
#二分累乗法 iDを法として
def fBiPow(iX,iN,iD):
    iY = 1
    while iN > 0:
        if iN % 2 == 0:
            iX = iX * iX % iD
            iN = iN // 2
        else:
            iY = iX * iY % iD
            iN = iN - 1
    return iY

aP = fPrimeCounter(iM)
if aP == [] :
    print (1)
else:
    iMax = max(aP) + iN - 1
    aM = [1] * (iMax + 1)
    #階乗 iD を法とした
    for i in range(1,iMax + 1):
        aM[i] = aM[i-1] * i  % iD
    aInvM = [1]* (iMax + 1)
    aInvM[iMax] = fBiPow(aM[iMax],iD-2,iD)
    #階乗の逆元 iD を法とした
    for i in range(iMax,0,-1):
        aInvM[i-1] = aInvM[i]*i % iD

    iRet = 1
    for i in aP:
        # i + iN -1  C  iN -1
        iRet *= aM[i+iN-1] * aInvM[iN-1] * aInvM[i] % iD
    iRet %= iD
    print(iRet)

Submission status: Time Limit Exceeded

Solution code:
iN,iM = [int(x) for x in input().split()]
iD = 10**9 +7 #法

def fPrimeCounter(iM):
    i = 2
    iS = iM ** 0.5 + 1
    aRet = []
    while i < iS or i <= iM  :
        iCounter = 0
        while iM % i == 0:
            iM = iM // i
            iCounter += 1
        if 0 < iCounter : aRet.append(iCounter)
        i += 1
    #if aRet == [] : aRet = [1]
    return aRet

#ABC042Dの流用
#二分累乗法 iDを法として
def fBiPow(iX,iN,iD):
    iY = 1
    while iN > 0:
        if iN % 2 == 0:
            iX = iX * iX % iD
            iN = iN // 2
        else:
            iY = iX * iY % iD
            iN = iN - 1
    return iY

aP = fPrimeCounter(iM)
if aP == [] :
    print (1)
else:
    iMax = max(aP) + iN - 1
    aM = [1] * (iMax + 1)
    #階乗 iD を法とした
    for i in range(1,iMax + 1):
        aM[i] = aM[i-1] * i  % iD
    aInvM = [1]* (iMax + 1)
    aInvM[iMax] = fBiPow(aM[iMax],iD-2,iD)
    #階乗の逆元 iD を法とした
    for i in range(iMax,0,-1):
        aInvM[i-1] = aInvM[i]*i % iD

    iRet = 1
    for i in aP:
        # i + iN -1  C  iN -1
        iRet *= aM[i+iN-1] * aInvM[iN-1] * aInvM[i] % iD
    iRet %= iD
    print(iRet)

Submission status: Time Limit Exceeded

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

def distribute(pos, full, tmp):
    return memo[tmp][pos]

# define search range
p_max = M // 2 # M is prime if M has a factor p (> p_max)
ip_up = max((1, int(math.log2(M)))) # MDE

#### O(MlogM) below (if M has a very large prime factor)
M_tmp = M
ips = []
for p in range(2, p_max + 1):
    if M_tmp % p > 0: continue
    # how many times M_tmp can be divided
    p_tmp = p
    for i_p in range(ip_up + 1):
        if M_tmp % p_tmp > 0: break
        p_tmp = p_tmp * p
    # calculate later
    ips.append(i_p)
    # next
    M_tmp = M_tmp // (p_tmp // p)
    if M_tmp == 1: break
#### O(Mlog M) above

#### O(N) below
# create memo
## init
if len(ips) > 0: ip_max = max(ips)
else: ip_max = 0
memo = [[None] * N for i in range(ip_max + 1)] # max ip
for j in range(N): memo[0][j] = 1
for i in range(1, ip_max + 1): memo[i][N - 1] = 1
## fill
for i in range(1, ip_max + 1):
    sum_tmp = 0
    vals = list(memo[i - 1])[::-1]
    p_memo = memo[i]
    for j, val in enumerate(vals):
        sum_tmp += val
        p_memo[N - 1 - j] = sum_tmp
#### O(N) above
        
# calculate ans
ans = 1
for i_p in ips: ans = (ans * distribute(0, i_p, i_p)) % (10 ** 9 + 7)

if M == 1: print(1)
elif ip_max < 1: print(N)
else: print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

mod = 1000000007

# nの素因数分解

def prime(n):
    d = Counter()
    i = 2
    while n != 1:
        while n%i == 0:
            n //= i
            d[i] += 1
        i += 1
    return d

# xのn乗を計算する
def mod_pow(x, n):
    if n == 0:
        return 1
    elif n % 2 == 0:
        half_x = mod_pow(x, n // 2)
        return half_x * half_x % mod
    else:
        return x * mod_pow(x, n-1) % mod

fact = [0] * 100099
inv = [0] * 100099
fact[0] = 1
inv[0] = 1
for k in range(1, 100099):
    fact[k] = fact[k-1] * k % mod
    inv[k] = mod_pow(fact[k], mod-2)

def nCr(n, r):
    return fact[n] * inv[r] % mod * inv[n-r] % mod

def solve():
    N, M = map(int, input().split())
    p = prime(M)
    s = 1
    for i in p.values():
        s *= nCr(i + N - 1, N - 1)
        s %= mod
    print(s)

solve()

Submission status: Time Limit Exceeded

Solution code:
mod = 1000000007

# nの素因数分解

def prime(n):
    d = []
    i = 2
    while n != 1:
        s = 0
        while n % i == 0:
            n /= i
            s += 1
        d.append(s)
        i += 1
    return d

# xのn乗を計算する
def mod_pow(x, n):
    if n == 1:
        return x
    elif n % 2 == 0:
        half_x = mod_pow(x, n // 2)
        return half_x * half_x % mod
    else:
        return x * mod_pow(x, n-1) % mod

fact = [0] * 100099
inv = [0] * 100099
fact[0] = 1
inv[0] = 1
for k in range(1, 100099):
    fact[k] = fact[k-1] * k % mod
    inv[k] = mod_pow(fact[k], mod-2)

def nCr(n, r):
    return fact[n] * inv[r] % mod * inv[n-r] % mod

def solve():
    N, M = map(int, input().split())
    p = prime(M)
    s = 1
    for i in p:
        s *= nCr(i + N - 1, N - 1)
        s %= mod
    print(s)

solve()

Submission status: Time Limit Exceeded

Solution code:
mod = 1000000007

# nの素因数分解


def prime(n):
    d = []
    i = 2
    while n != 1:
        s = 0
        while n % i == 0:
            n /= i
            s += 1
        d.append(s)
        i += 1
    return d


# xのn乗を計算する
def mod_pow(x, n):
    if n == 0:
        return 1
    elif n % 2 == 0:
        half = int(n / 2)
        half_x = mod_pow(x, half)
        return half_x * half_x % mod
    else:
        return x * mod_pow(x, n - 1) % mod


def nCr(n, r):
    x = 1
    r = min(r, n - r)
    for i in range(r):
        x *= n - i
        x %= mod
        x *= mod_pow(i + 1, mod - 2)
        x %= mod
    return x


def solve():
    N, M = map(int, input().split())
    p = prime(M)
    s = 1
    for i in p:
        s *= nCr(i + N - 1, N - 1)
        s %= mod
    print(s)


solve()

Submission status: Time Limit Exceeded

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

def distribute(pos, full, tmp):
    return memo[tmp][pos]

# define search range
p_max = int(M / 2) # M is prime if M has a factor p (> p_max)
ip_max = int(math.log2(M))

# create memo
memo = [[None] * N for i in range(ip_max + 1)] # max ip
for j in range(N): memo[0][j] = 1
for i in range(1, ip_max + 1): memo[i][N - 1] = 1

M_tmp = M
ans = 1
ip_tmp = 0 # temporary size of memo
for p in range(2, p_max + 1):
    # how many times M_tmp can be divided
    p_tmp = p
    for i_p in range(ip_max + 1):
        if M_tmp % p_tmp > 0: break
        p_tmp = p_tmp * p
    # escape if M_tmp cannot be divided
    if i_p < 1: continue
    # ans update (dp)
    ## expand memo if necessary
    if i_p > ip_tmp:
        for i in range(ip_tmp + 1, i_p + 1):
            memo_tmp = [0] * N
            sum_tmp = 0 # memo[i - 1][N - 1]
            vals = list(memo[i - 1])[::-1]
            for j, val in enumerate(vals):
                sum_tmp += val
                memo_tmp[N - 1 - j] = sum_tmp
            memo[i] = list(memo_tmp)
    ## search and count
    ans_tmp = distribute(0, i_p, i_p)
    ## add
    ans = (ans * ans_tmp) % (10 ** 9 + 7)
    # next
    M_tmp = M_tmp // (p_tmp // p)
    if M_tmp == 1: break

print(ans)

Submission status: Time Limit Exceeded

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

mod = 1000000007

f = [] # 素因数分解(指数部のみ)

for p in range(2, M): # 素因数分解
    e = 0
    while M%p == 0:
        e += 1
        M /= p
    
    if e>0:
        f.append(e)
    
    if M == 1:
        break

def pw(a, e):
    if e == 1:
        return a
    p = pw(a, e // 2)
    if e%2 == 1:
        return p * p % mod * a % mod
    else:
        return p * p % mod

# fact, inv の計算
fact = [1] * 100040
inv = [1] * 100040
for k in range(1, 100040):
    fact[k] = fact[k-1] * k % mod
    inv[k] = pw(fact[k], mod-2)

ans = 1
for e in f:
    ans = ans * fact[e+N-1] % mod * inv[e] % mod * inv[N-1] % mod # N_H_e (重複組合せ)

print(ans)

Submission status: Time Limit Exceeded

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

mod = 1000000007

f = [] # 素因数分解(指数部のみ)

for p in range(2, M): # 素因数分解
    e = 0
    while M%p == 0:
        e += 1
        M /= p
    
    if e>0:
        f.append(e)
    
    if M == 1:
        break

def pw(a, e):
    if e == 1:
        return a
    p = pw(a, e // 2)
    if e%2 == 1:
        return p * p % mod * a % mod
    else:
        return p * p % mod

# fact, inv の計算
fact = [1] * 100040
inv = [1] * 100040
for k in range(1, 100040):
    fact[k] = fact[k-1] * k % mod
    inv[k] = pw(fact[k], mod-2)

def combine(n, k):
    return fact[n] * inv[k] % mod * inv[n-k] % mod

ans = 1
for e in f:
    ans *= combine(e+N-1, e) # N_H_e (重複組合せ)
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

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

# def distribute(pos, full, tmp):
#     # read memo
#     if memo[pos][tmp] != None: return memo[pos][tmp]
#     # end
#     if tmp == 0: return 1
#     # next
#     ret = 0
#     if pos < N - 1:
#         for i in range(tmp + 1): ret += distribute(pos + 1, full, tmp - i)
#     else: ret += 1
#     # print("###", pos, tmp, ret)
#     # write memo
#     if memo[pos][tmp] != None: memo[pos][tmp] = ret
#     return ret
def distribute(pos, full, tmp):
    return memo[pos][tmp]

# define search range
p_max = int(M / 2) # M is prime if M has a factor p (> p_max)
ip_max = int(math.log2(M))

# create memo
memo = [[None] * (ip_max + 1) for i in range(N)] # max ip
for i in range(N): memo[i][0] = 1
for j in range(1, ip_max + 1): memo[N - 1][j] = 1

M_tmp = M
ans = 1
ip_tmp = 0 # temporary size of memo
for p in range(2, p_max + 1):
    # how many times M_tmp can be divided
    p_tmp = p
    for i_p in range(ip_max + 1):
        if M_tmp % p_tmp > 0: break
        p_tmp = p_tmp * p
    # escape if M_tmp cannot be divided
    if i_p < 1: continue
    # ans update (dp)
    ## expand memo
    if i_p > ip_tmp: 
        for j in range(ip_tmp + 1, i_p + 1):
            memo_tmp = memo[N - 1][j - 1]
            for i in list(range(N - 1))[::-1]:
                memo_tmp += memo[i][j - 1]
                memo[i][j] = memo_tmp
    ## search and count
    ans_tmp = distribute(0, i_p, i_p)
    ## add
    ans = (ans * ans_tmp) % (10 ** 9 + 7)
    # next
    M_tmp = M_tmp // (p_tmp // p)
    if M_tmp == 1: break

print(ans)

Submission status: Time Limit Exceeded

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

mod = 1000000007

f = [] # 素因数分解(指数部のみ)

for p in range(2, M): # 素因数分解
    e = 0
    while M%p == 0:
        e += 1
        M /= p
    
    if e>0:
        f.append(e)
    
    if M == 1:
        break

def pw(a, e):
    if e == 1:
        return a
    p = pw(a, e // 2)
    if e%2 == 1:
        return p * p % mod * a % mod
    else:
        return p * p % mod

# fact, inv の計算
fact = [1]
inv = [1]
for k in range(1, 100033):
    fact.append(fact[k-1] * k % mod)
    inv.append(pw(fact[k], mod-2))

def combine(n, k):
    return fact[n] * inv[k] % mod * inv[n-k] % mod

ans = 1
for e in f:
    ans *= combine(e+N-1, e) # N_H_e (重複組合せ)
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

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

mod = 1000000007

f = [] # 素因数分解(指数部のみ)

for p in range(2, M): # 素因数分解
    e = 0
    while M%p == 0:
        e += 1
        M /= p
    
    if e>0:
        f.append(e)
    
    if M == 1:
        break

def pw(a, e):
    if e == 0:
        return 1
    p = pw(a, e//2)
    if e%2 == 1:
        return p * p % mod * a % mod
    else:
        return p * p % mod; 

# fact, inv の計算
fact = [1]
inv = [1]
for k in range(1, 100064):
    fact.append(fact[k-1] * k % mod)
    inv.append(pw(fact[k], mod-2))

def combine(n, k):
    return fact[n] * inv[k] % mod * inv[n-k] % mod

ans = 1
for e in f:
    ans *= combine(e+N-1, e) # N_H_e (重複組合せ)
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def divisions(n):
    sq = int(math.sqrt(n)+1)
    d = collections.defaultdict(int)
    while n % 2 == 0:
        n //= 2
        d[2] += 1
    i = 3
    while n > 1 and sq >= i:
        if n % i == 0:
            n //= i
            d[i] += 1
        else:
            i += 2

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

    r = [1]
    for k, v in d.items():
        for c in r[:]:
            for i in range(1,v+1):
                r.append(c*(k**i))

    return sorted(r)

def main():
    n,m = LI()
    d = divisions(m)
    dd = {}
    for c in d:
        dd[c] = divisions(c)[1:]
    dp = collections.defaultdict(int)
    dp[m] = 1
    for i in range(n-1):
        for k,v in sorted(dp.items()):
            for c in dd[k]:
                kc = k // c
                dp[kc] += v
                dp[kc] %= mod
    r = sum(dp.values())
    r %= mod

    return r


print(main())

Submission status: Time Limit Exceeded

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

map = {}
i = 2
while m != 1:
    if m % i == 0 :
        m = m / i
        if i in map:
            map[i] += 1
        else:
            map[i] = 1
    else:
        i += 1
sum = 1
for i in map:
    tmpn = n + map[i] - 1
    c = 1
    d = 1
    e = 1
    for j in range(map[i]):
        c = c * (tmpn - j)
        d = d * (map[i] - j)
    e = e * c // d
    
    sum = sum * e % 1000000007
print(sum )

Submission status: Time Limit Exceeded

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

map = {}
i = 2
while m != 1:
    if m % i == 0 :
        m = m / i
        if i in map:
            map[i] += 1
        else:
            map[i] = 1
    else:
        i += 1
sum = 1
for i in map:
    tmpn = n + map[i] - 1
    c = 1
    d = 1
    e = 1
    for j in range(map[i]):
        c = c * (tmpn - j)
        d = d * (map[i] - j)
    e = e * c // d
    
    sum = sum * e
print(sum % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import unittest
import math

MOD = 10**9+7


def func(n,m):
    fac = [1 for _ in range(n+100)]
    finv = [1 for _ in range(n+100)]
    inv = [1 for _ in range(n+100)]
    for i in range(2,n+100):
        fac[i] = (fac[i-1]*i)%MOD
        inv[i] = (MOD - inv[MOD%i] * (MOD//i))%MOD
        finv[i] = (finv[i-1]*inv[i])%MOD

    def comb(a,b):
        return (fac[a]*((finv[b]*finv[a-b])%MOD))%MOD

    fact = {}
    for x in range(2, m+1):
        while m%x==0:
            if x not in fact:
                fact[x] = 0
            fact[x] += 1
            m = m//x
        if m==1:
            break

    ret = 1
    for k in fact.values():
        ret *= comb(k+n-1,k)
        ret %= MOD
    return ret

class Test(unittest.TestCase):
    def test(self):
        self.assertEqual(func(2,6), 4)
        self.assertEqual(func(3,12), 18)
        self.assertEqual(func(100000, 1000000000), 957870001)
        self.assertEqual(func(2,3), 2)

if __name__ == '__main__':
    n,m = map(int, input().split())
    print(func(n,m))
    # unittest.main()

Submission status: Time Limit Exceeded

Solution code:
mod = 1000000007

# nの素因数分解


def prime(n):
    d = []
    i = 2
    while n != 1:
        s = 0
        while n % i == 0:
            n /= i
            s += 1
        d.append(s)
        i += 1
    return d


# xのn乗を計算する
def mod_pow(x, n):
    if n == 0:
        return 1
    elif n % 2 == 0:
        half = int(n / 2)
        half_x = mod_pow(x, half)
        return half_x * half_x % mod
    else:
        return x * mod_pow(x, n - 1) % mod


def nCr(n, r):
    x = 1
    r = min(r, n - r)
    for i in range(r):
        x *= n - i
        x %= mod
        x *= mod_pow(i + 1, mod - 2)
        x %= mod
    return x


def solve():
    N, M = map(int, input().split())
    p = prime(M)
    s = 1
    for i in p:
        s *= nCr(i + N - 1, N - 1)
        s %= mod
    print(s)


solve()

Submission status: Time Limit Exceeded

Solution code:
def cal_factors(num):
    factors = {}
    mod = 2
    while num >= 2:
        if num % mod == 0:
            if mod in factors:
                factors[mod] += 1
            else:
                factors[mod] = 1
            num //= mod
        else:
            mod += 1

    return factors


def comb(n, r, mod):
    result = 1
    r = min(r, n-r)
    for i in range(n, n-r, -1):
        result *= i
    for i in range(2, r+1):
        result //= i
    result %= mod

    return result


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

mod = 1000000000 + 7
factors = cal_factors(m)
ans = 1
for v in factors.values():
    ans *= comb(v + n - 1, v, mod)
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
import collections


mod = 1000000007
sys.setrecursionlimit(mod)
fact = {1: 1}


def run(n, m):
    # print('{}を{}個の数列で表現'.format(m, n))
    ans = 1
    primes = []
    for i in range(2, m):
        if m == 1:
            break
        if i*i > m:
            break
        if m % i == 0:
            cnt = 0
            while m % i == 0:
                cnt += 1
                m //= i
                primes.append(i)
            ans *= comb(cnt+n-1, n-1)
            ans %= mod
    # counts = collections.Counter(primes)
    # print(counts)
    # for (_, v) in counts.items():
    #     ans *= comb(v+n-1, n-1)
    #     ans %= mod
    if m != 1:
        ans *= n
        ans %= mod
    return ans


def comb(n, r):
    mul = math.factorial(n) // math.factorial(n - r)
    div = math.factorial(r)
    # mul = factorial(n) // factorial(n - r)
    # div = factorial(r)
    mul %= mod
    div %= mod
    return (mul * modpow(div, (mod-2))) % mod


'''
def factorial(n):
    if n in fact:
        return fact[n]
    else:
        fact[n] = n*factorial(n-1)
        return fact[n]
'''


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


def main():
    n, m = map(int, input().split())
    print(run(n, m))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
import collections


mod = 1000000007
sys.setrecursionlimit(mod)
fact = {1: 1}


def run(n, m):
    # print('{}を{}個の数列で表現'.format(m, n))
    ans = 1
    primes = []
    for i in range(2, m):
        if m == 1:
            break
        if i*i > m:
            break
        if m % i == 0:
            cnt = 0
            while m % i == 0:
                cnt += 1
                m //= i
                primes.append(i)
            # ans *= comb(cnt+n-1, n-1)
            # ans %= mod
    counts = collections.Counter(primes)
    # print(counts)
    for (_, v) in counts.items():
        ans *= comb(v+n-1, n-1)
        ans %= mod
    if m != 1:
        ans *= n
        ans %= mod
    return ans


def comb(n, r):
    mul = math.factorial(n) // math.factorial(n - r)
    div = math.factorial(r)
    # mul = factorial(n) // factorial(n - r)
    # div = factorial(r)
    mul %= mod
    div %= mod
    return (mul * modpow(div, (mod-2))) % mod


'''
def factorial(n):
    if n in fact:
        return fact[n]
    else:
        fact[n] = n*factorial(n-1)
        return fact[n]
'''


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


def main():
    n, m = map(int, input().split())
    print(run(n, m))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def cal_factors(num):
    factors = []
    mod = 2
    while num >= 2:
        if num % mod == 0:
            factors.append(mod)
            num //= mod
        else:
            mod += 1

    return factors


def comb(n, r, mod):
    result = 1
    r = min(r, n-r)
    for i in range(n, n-r, -1):
        result *= i
    for i in range(2, r+1):
        result //= i
    result %= mod

    return result


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

mod = 1000000000 + 7
factors = Counter(cal_factors(m))
ans = 1
for v in factors.values():
    ans *= comb(v + n - 1, v, mod)
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def cal_factors(num):
    factors = []
    mod = 2
    while num >= 2:
        if num % mod == 0:
            factors.append(mod)
            num //= mod
        else:
            mod += 1

    return factors


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

    return result


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

mod = 1000000000 + 7
factors = Counter(cal_factors(m))
ans = 1
for v in factors.values():
    ans *= comb(v + n - 1, v, mod)
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
import collections


mod = 1000000007
sys.setrecursionlimit(mod)
fact = {1: 1}


def run(n, m):
    # print('{}を{}個の数列で表現'.format(m, n))
    ans = 1
    primes = []
    for i in range(2, m):
        if m == 1:
            break
        if m % i == 0:
            cnt = 0
            while m % i == 0:
                cnt += 1
                m //= i
                primes.append(i)
            # ans *= comb(cnt+n-1, n-1)
            # ans %= mod
    counts = collections.Counter(primes)
    # print(counts)
    for (_, v) in counts.items():
        ans *= comb(v+n-1, n-1)
        ans %= mod
    return ans


def comb(n, r):
    mul = math.factorial(n) // math.factorial(n - r)
    div = math.factorial(r)
    # mul = factorial(n) // factorial(n - r)
    # div = factorial(r)
    mul %= mod
    div %= mod
    return (mul * modpow(div, (mod-2))) % mod


'''
def factorial(n):
    if n in fact:
        return fact[n]
    else:
        fact[n] = n*factorial(n-1)
        return fact[n]
'''


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


def main():
    n, m = map(int, input().split())
    print(run(n, m))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math

N, M = map(int, input().split())
max = int(math.sqrt(M))
mod = 7 + 10**9
F = []

def Prime(i): #素数であればTrueを返す
    root = math.sqrt(i)
    j, div = 2, False
    while j <= root:
        if i % j == 0:
            div = True
            break
        j += 1
    return (True if not div else False)

def comb(n, r):
    ans = math.factorial(n) // (math.factorial(n-r) * math.factorial(r))
    return ans % mod


ans = 1
for i in range(2, max + 1):
    if M % i == 0:
        div = M // i
        if Prime(i):
            pow = 0
            while M % (i ** (pow+1)) == 0:
                pow += 1
            ans *= comb(pow + N -1, pow)
            ans %= mod
        if Prime(div):
            pow = 0
            while M % (i ** (pow+1)) == 0:
                pow += 1
            ans *= comb(pow + N - 1, pow)
            ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def comb(a, b):
    b = min(b, a - b)

    res = 1
    for i in range(b):
        res *= (a - i)
        res %= MOD

    for div in range(1, b + 1):
        res = res * pow(div, MOD - 2, MOD) % MOD
    return res


def prime_factorization(x):
    res = []
    i = 2
    left = x + 0
    while True:
        if (i * i > x) and (left == 1):
            break
        cnt = 0
        while left % i == 0:
            left /= i
            cnt += 1
        if cnt > 0:
            res.append(cnt)
        # print(i, res)
        i += 1
    return res


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

MOD = 10 ** 9 + 7

ans = 1
for power in prime_factorization(m):
    ans *= comb(n - 1 + power, power)
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def comb(a, b):
    if b > a - b:
        return comb(a, a - b)
    mul = 1
    div = 1
    for i in range(b):
        mul *= (a - i)
        mul %= MOD

        div *= (i + 1)
        div %= MOD
    res = mul * pow(div, MOD - 2, MOD) % MOD
    return res


def prime_factorization(x):
    res = []
    i = 2
    left = x + 0
    while True:
        if (i * i > x) and (left == 1):
            break
        cnt = 0
        while left % i == 0:
            left /= i
            cnt += 1
        if cnt > 0:
            res.append(cnt)
        # print(i, res)
        i += 1
    return res


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

MOD = 10 ** 9 + 7

ans = 1
for power in prime_factorization(m):
    ans *= comb(n - 1 + power, power)
ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def mod_power(a, f_power):
    """
    a の p 乗を求めるアルゴリズム
    計算量はO(log(f_power))
    """
    if f_power == 0:
        return 1
    if f_power % 2 == 0:
        half = mod_power(a, f_power / 2)
        # half : a ** (power /2) の 2乗で a ** power を求める
        return half * half % MOD
    else:
        return a * mod_power(a, f_power - 1) % MOD


def comb(a, b):
    if b > a - b:
        return comb(a, a - b)
    # res = 1
    mul = 1
    div = 1
    for i in range(b):
        # res *= (a - i)
        # res /= (i + 1)
        mul *= (a - i)
        # mul %= MOD

        div *= (i + 1)
        # div %= MOD
    res = mul * mod_power(div, MOD - 2) % MOD
    return res


def prime_factorization(x):
    res = []
    i = 2
    left = x + 0
    while True:
        if (i * i > x) and (left == 1):
            break
        cnt = 0
        while left % i == 0:
            left /= i
            cnt += 1
        if cnt > 0:
            res.append(cnt)
        # print(i, res)
        i += 1
    return res


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

MOD = 10 ** 9 + 7

ans = 1
for power in prime_factorization(m):
    ans *= comb(n - 1 + power, power)
ans %= MOD

print(ans)
# print(prime_factorization(6))

Submission status: Time Limit Exceeded

Solution code:
def mod_power(a, f_power):
    """
    a の p 乗を求めるアルゴリズム
    計算量はO(log(f_power))
    """
    if f_power == 0:
        return 1
    if f_power % 2 == 0:
        half = mod_power(a, f_power / 2)
        # half : a ** (power /2) の 2乗で a ** power を求める
        return half * half % MOD
    else:
        return a * mod_power(a, f_power - 1) % MOD


def comb(a, b):
    if b > a - b:
        return comb(a, a - b)
    # res = 1
    mul = 1
    div = 1
    for i in range(b):
        # res *= (a - i)
        # res /= (i + 1)
        mul *= (a - i)
        mul %= MOD

        div *= (i + 1)
        div %= MOD
    res = mul * mod_power(div, MOD - 2) % MOD
    return res


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

MOD = 10 ** 9 + 7

ans = 1
i = 2
left = m + 0
while True:
    if (i * i > m) and (left == 1):
        break
    power = 0
    while left % i == 0:
        left /= i
        power += 1
    if power > 0:
        ans *= comb(n - 1 + power, power)
    i += 1

ans %= MOD

print(ans)