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: Wrong Answer

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

def compute_divisors(num):
    divisors = set()
    for i in range(1, int(num**.5) + 1):
        if num % i == 0:
            divisors.add(i)
            divisors.add(num // i)
    return divisors

div = sorted(compute_divisors(M))
for d in div:
    dp[1, d] = 1
divn = len(div)
print(divn)
for i in range(2, N + 1):
    for j in range(divn):
        for k in range(j, divn):
            if div[k] % div[j] == 0:
                dp[i, div[k]] += dp[i-1, div[j]]
                dp[i, div[k]] %= MOD
print(dp[N, M])

Submission status: Time Limit Exceeded

Solution code:
#素因数分解
def soinsu_bunkai(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

from math import factorial
def kumiawase_num(n, r): # 組み合わせ n「C」r
    if  n<r:
        return 0
    return factorial(n) // (factorial(n - r) * factorial(r))

# 初期入力
from collections import Counter
import sys
input = sys.stdin.readline  #文字列では使わない
mod =10**9 +7
N,M = map(int, input().split())
a =soinsu_bunkai(M)
ans =1
for i in a.values():
    x =kumiawase_num(N +i -1,i)
    x %=mod
    ans *=x
print(ans %mod)

Submission status: Time Limit Exceeded

Solution code:
from typing import List, Dict


def cumlative_sum(x: List) -> List:
    '''累積和'''
    res = [0]
    for i, v in enumerate(x):
        res.append(res[i] + v)
    return res
def prime_factorization(x: int) -> Dict[int, int]:
    '''
    素因数分解: output = Dict[素因数, 乗数]

    最大の素因数は高々sqrt(x)以下であることを利用して高速化
    '''
    divided = x
    res = {}
    max_possible_factor = int(x**0.5)
    for num in range(2, max_possible_factor + 1):
        if divided % num == 0:
            counter = 0
            while divided % num == 0:
                counter += 1
                divided //= num
            res[num] = counter
    
    if divided != 1:
        res[divided] = 1
    
    if res == {}:
        res[x] = 1

    return res
def factorial(x: int) -> int:
    '''階乗'''
    res = 1
    while x > 1:
        res *= x
        x -= 1
    return res
def combination(x: int, y: int) -> int:
    '''xCy'''
    res = 1
    for _ in range(y):
        res *= x
        x -= 1
    res //= factorial(y)
    return res

n, m = map(int, input().split())
prime_factors_dict = prime_factorization(m)
ans = 1
for power in prime_factors_dict.values():
    ans *= combination(power+n-1, n-1)
    if ans > 1000000000 + 7:
        ans %= 1000000000 + 7
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from math import factorial

MOD = 10 ** 9 + 7


def factorize(n):
    facts = defaultdict(int)
    while n % 2 == 0:
        n //= 2
        facts[2] += 1
    m = 3
    while m * m <= n:
        while n % m == 0:
            facts[m] += 1
            n //= m
        m += 2
    if 1 < n:
        facts[n] += 1
    return facts


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


N, M = map(int, input().split())
factors = factorize(M)
ans = 1
for p, e in factors.items():
    ans = ans * nCr(N - 1 + e, e) % MOD
print(ans)

Submission status: Time Limit Exceeded

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

# 因数分解
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
a = prime_factorize(M)
c = Counter(a)
l = []
for i in c.values():
    # 階乗
    # 重複組み合わせ
    l.append(math.factorial(N+i-1)//(math.factorial(N-1)*math.factorial(i)))
ans = 1
for i in l:
    ans *= i
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
def input(): return sys.stdin.readline().strip()
mod = 10**9+7

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

def get_sieve_of_eratosthenes(n):
    """
    エラトステネスの篩
    """
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        return []
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit < p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
    return data

def main():
    comb = Combination(5 * 10**5)
    N, M = map(int, input().split())
    primes = get_sieve_of_eratosthenes(M)
    cand = []
    for p in primes:
        num = 0
        while M % p == 0:
            M //= p
            num += 1
        if num > 0: cand.append(num)

    ans = 1
    for num in cand:
        ans *= comb(num + (N - 1), num)
        ans %= mod
    print(ans)





if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import collections,math,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,M = LI()
ans = 1
def prime_factor(num):
    prime_factor = collections.defaultdict(int)
    for i in range(2,int(num**0.5)+1):
        while num%i==0:
            prime_factor[i] += 1
            num //= i
    if num>1:
        prime_factor[num]=1
    return prime_factor
for v in prime_factor(M).values():
    ans *= math.factorial(v+N-1)//math.factorial(v)//math.factorial(N-1)
    ans %= 10**9+7
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections as col
import numpy as np
import math as ma
import scipy.misc as spm #miscellaneous

MOD = 10**9 + 7
def inv(a): return pow(a, MOD-2, MOD)
def comb(n,r,MOD):
    ans = 1
    for i in range(r): # r-i==0でbreak
        ans *= n-i
        ans *= inv(r-i)
        ans %= MOD
    return ans


def prime(n):
    ans = []
    for i in range(2, int(n**0.5)+1):
        while not n%i: n //= i; ans.append(i)
    if n != 1: ans.append(n)
    return ans

n,m = map(int,input().split())
cnt = col.Counter(prime(m))

ans = 1
for key,val in cnt.items():
    #ans *= comb(val + n-1, n-1)
    ans *= comb(val + n-1, n-1, MOD)
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections as col
import numpy as np
import math as ma
import scipy.misc as spm #miscellaneous

MOD = 10**9 + 7
def inv(a): return pow(a, MOD-2, MOD)
def comb(n,r,MOD):
    ans = ma.factorial(n) * inv(ma.factorial(r)) * inv(ma.factorial(n-r))
    return ans%MOD

def prime(n):
    ans = []
    for i in range(2, int(n**0.5)+1):
        while not n%i: n //= i; ans.append(i)
    if n != 1: ans.append(n)
    return ans

n,m = map(int,input().split())
cnt = col.Counter(prime(m))

ans = 1
for key,val in cnt.items():
    #ans *= comb(val + n-1, n-1)
    ans *= comb(val + n-1, n-1, MOD)
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections as col
import numpy as np
import math as ma
import scipy.misc as spm #miscellaneous

MOD = 10**9 + 7
def inv(a): return pow(a, MOD-2, MOD)
def comb(n,r,MOD):
    ans = ma.factorial(n)%MOD * inv(ma.factorial(r)) * inv(ma.factorial(n-r))
    return ans%MOD

def prime(n):
    ans = []
    for i in range(2, int(n**0.5)+1):
        while not n%i: n //= i; ans.append(i)
    if n != 1: ans.append(n)
    return ans

n,m = map(int,input().split())
cnt = col.Counter(prime(m))

ans = 1
for key,val in cnt.items():
    #ans *= comb(val + n-1, n-1)
    ans *= comb(val + n-1, n-1, MOD)
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections as col
import itertools as ite
import numpy as np
import math as ma

MOD = 10**9 + 7
def inv(a): return pow(a, MOD-2, MOD)
def comb(n,r):
    ans = ma.factorial(n)%MOD * inv(ma.factorial(r)) * inv(ma.factorial(n-r))
    return ans%MOD
def prime(n):
    ans = []
    for i in range(2, int(n**0.5)+1):
        while not n%i: n //= i; ans.append(i)
    if n != 1: ans.append(n)
    return ans

n,m = map(int,input().split())
cnt = col.Counter(prime(m))

ans = 1
for key,val in cnt.items():
    ans *= comb(val + n-1, n-1)
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

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

import sys
import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
        
    class Eratos:
        def __init__(self, num):
            assert(num >= 1)
            self.table_max = num
            # self.table[i] は i が素数かどうかを示す (bool)
            self.table = [False if i == 0 or i == 1 else True for i in range(num+1)]
            for i in range(2, int(math.sqrt(num)) + 1):
                if self.table[i]:
                    for j in range(i ** 2, num + 1, i):    # i**2 からスタートすることで定数倍高速化できる
                        self.table[j] = False
            # self.table_max 以下の素数を列挙したリスト
            self.prime_numbers = [2] if self.table_max >= 2 else []
            for i in range(3, self.table_max + 1, 2):
                if self.table[i]:
                    self.prime_numbers.append(i)
        
        def is_prime(self, num):
            """
            >>> e = Eratos(100)
            >>> [i for i in range(1, 101) if e.is_prime(i)]
            [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
            """
            assert(num >= 1)
            if num > self.table_max:
                raise ValueError('Eratos.is_prime(): exceed table_max({}). got {}'.format(self.table_max, num))
            return self.table[num]
        
        def prime_factorize(self, num):
            """
            >>> e = Eratos(10000)
            >>> e.prime_factorize(6552)
            {2: 3, 3: 2, 7: 1, 13: 1}
            """
            assert(num >= 1)
            if int(math.sqrt(num)) > self.table_max:
                raise ValueError('Eratos.prime_factorize(): exceed prime table size. got {}'.format(num))
            factorized_dict = dict()    # 素因数分解の結果を記録する辞書
            candidate_prime_numbers = [i for i in range(2, int(math.sqrt(num)) + 1) if self.is_prime(i)]
            # n について、√n 以下の素数で割り続けると最後には 1 or 素数となる
            # 背理法を考えれば自明 (残された数が √n より上の素数の積であると仮定。これは自明に n を超えるため矛盾)
            for p in candidate_prime_numbers:
                # これ以上調査は無意味
                if num == 1:
                    break
                while num % p == 0:
                    num //= p
                    try:
                        factorized_dict[p]
                    except KeyError:
                        factorized_dict[p] = 0
                    finally:
                        factorized_dict[p] += 1
            if num != 1:
                factorized_dict[num] = 1
            return factorized_dict
    

    n, m = mi()
    eratos = Eratos(m)
    d = eratos.prime_factorize(m)
    # print(d)

    FACT = [1] * (n + int(math.log2(m)) + 1)
    for i in range(2, n + int(math.log2(m)) + 1):
        FACT[i] = (FACT[i-1] * i) % mod
    
    def comb(n, r, m):
        numerator = FACT[n]
        denominator = pow(FACT[n-r] * FACT[r], m - 2, m)
        return (numerator * denominator) % m

    ans = 1
    for _, k in d.items():
        ans = (ans * comb(k + n - 1, k, mod)) % mod
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

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

def prime_factor(n):
    ass = []
    for i in range(2,int(n**0.5)+1):
        count=0
        while n % i==0:
            count+=1
            n = n//i
        if count!=0:
            ass.append((i,count))
    if n != 1:
        ass.append((n,1))
    return ass


ass = prime_factor(m)
ans = 1
for i, amount in ass:
  ans = ans * len(tuple(itertools.combinations_with_replacement(range(n),amount))) % mod
print(ans)
# print(ass)

Submission status: Time Limit Exceeded

Solution code:
class Calc:
    def __init__(self, max_value, mod):
        """combination(max_value, all)"""
        fact = [-1] * (max_value + 1)
        fact[0] = 1
        fact[1] = 1
        for x in range(2, max_value + 1):
            fact[x] = x * fact[x - 1] % mod

        invs = [1] * (max_value + 1)
        invs[max_value] = pow(fact[max_value], mod - 2, mod)
        for x in range(max_value - 1, 0, -1):
            invs[x] = invs[x + 1] * (x + 1) % mod

        self.fact = fact
        self.invs = invs
        self.mod = mod

    def combination(self, n, r):
        if n - r < r:
            return self.combination(n, n - r)
        if r < 0:
            return 0
        if r == 0:
            return 1
        if r == 1:
            return n
        return self.fact[n] * self.invs[r] * self.invs[n - r] % self.mod


def main():
    MOD = 10 ** 9 + 7

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

    def decom(n) -> list:
        ret = []

        d = 2
        cnt = 0
        while n % d == 0:
            n //= d
            cnt += 1
        ret.append(cnt)

        d = 3
        while n > 1:
            cnt = 0
            while n % d == 0:
                n //= d
                cnt += 1
            ret.append(cnt)
            d += 2

        return ret

    dlis = decom(M)

    cal = Calc(max_value=N + 30, mod=MOD)

    ans = 1
    for cnt in dlis:
        ans = (ans * cal.combination(N + cnt - 1, cnt)) % MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
class Calc:
    def __init__(self, max_value, mod):
        """combination(max_value, all)"""
        fact = [-1] * (max_value + 1)
        fact[0] = 1
        fact[1] = 1
        for x in range(2, max_value + 1):
            fact[x] = x * fact[x - 1] % mod

        invs = [1] * (max_value + 1)
        invs[max_value] = pow(fact[max_value], mod - 2, mod)
        for x in range(max_value - 1, 0, -1):
            invs[x] = invs[x + 1] * (x + 1) % mod

        self.fact = fact
        self.invs = invs
        self.mod = mod

    def combination(self, n, r):
        if n - r < r:
            return self.combination(n, n - r)
        if r < 0:
            return 0
        if r == 0:
            return 1
        if r == 1:
            return n
        return self.fact[n] * self.invs[r] * self.invs[n - r] % self.mod


def main():
    MOD = 10 ** 9 + 7

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

    def decom(n) -> list:
        ret = []

        d = 2
        cnt = 0
        while n % d == 0:
            n //= d
            cnt += 1
        ret.append((d, cnt))

        d = 3
        while n > 1:
            cnt = 0
            while n % d == 0:
                n //= d
                cnt += 1
            ret.append((d, cnt))
            d += 1

        return ret

    dlis = decom(M)

    cal = Calc(max_value=N + 30, mod=MOD)

    ans = 1
    for _, cnt in dlis:
        ans = (ans * cal.combination(N + cnt - 1, cnt)) % MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd
import sys
import math
n, m = map(int, input().split())
dic = dd(int)

#M=1
if m == 1:
    print(1)
    sys.exit()
elif n == 1:
    print(1)
    sys.exit()

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

for i in range(2, math.ceil(m**0.5) + 3):
    while m % i == 0:
        m //= i
        dic[i] += 1
else:
    if m != 1:
        dic[m] = 1
#print(dic)

ans = 1
mod = 10**9 + 7
for count in dic.values():
    ans *= combinations_count(count + n - 1, n-1) % mod

print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
def comb(n,k,p):
  from math import factorial
  if n<0 or k<0 or n<k:return 0
  if n==0 and k==0:return 1
  a=factorial(n)%p
  b=factorial(k)%p
  c=factorial(n-k)%p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  if b==0:
    return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return (d*d)%p
  else:
    return (a*power_func(a,b-1,p))%p
n,m=map(int,input().split())
mod=10**9+7
d=[]
for i in range(2,int(m**0.5)+1):
  if m%i==0:
    cnt=0
    while m%i==0:
      m//=i
      cnt+=1
    d.append(cnt)
if m>1:
  d.append(1)
ans=1
for k in d:
  ans=(ans*comb(k+n-1,k,mod))%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

def factor(n):
    i = 2
    r = []
    while i * i <= n:
        if n % i == 0:
            c = 0
            while n % i == 0:
                c += 1
                n //= i
            r.append((i, c))
    if n > 1:
        r.append((n, 1))
    return r

class nCrMod():
    def __init__(self, mod):
        self.mod = mod
        self.fac = [1, 1]
        self.finv = [1, 1]
        self.inv = [0, 1]

    def prep(self, n):
        mod = self.mod
        f, fi = self.fac[-1], self.finv[-1]
        for i in range(len(self.fac), n + 1):
            fn = f * i % mod
            v = -self.inv[mod % i] * (mod // i) % mod
            fin = fi * v % mod
            f, fi = fn, fin
            self.fac.append(f)
            self.finv.append(fi)
            self.inv.append(v)

    def __call__(self, n, r):
        if len(self.fac) <= n:
            self.prep(n)
        return self.fac[n] * self.finv[r] * self.finv[n - r] % self.mod

def main():
    N, M = map(int, input().split())
    mod = 10**9 + 7
    nCr = nCrMod(mod)
    f = factor(M)
    r = 1
    for p, q in f:
        r = r * nCr(N + q - 1, q) % mod
    return r

print(main())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
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

N,M=map(int,list(input().split(" ")))
mod=10**9+7
def factor(M):
    i=2
    lis=[]
    if M%i==0:
        k=1
        M//=2
        while M%2==0:
            k+=1
            M//=2
        lis.append([2,k])
    i+=1
    while M!=1:
        if M%i==0:
            k=1
            M//=i
            while M%i==0:
                k+=1
                M//=i
            lis.append([i,k])
        i+=2
    return lis

fac=np.array(factor(M))
ans=1
for i in range(len(fac)):
    ans*=cmb(N+fac[i][1]-1,N-1)
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
mod = pow(10, 9) + 7
d = []
d.append([1 for _ in range(M + 1)])
d[0][0] = 0

for i in range(0, N - 1):
    d.append([])
    for j in range(M + 1):
        d[i + 1].append(sum([d[i][int(j / k)] for k in range(1, j + 1) if j % k == 0]) % mod)
   
print(d[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
class Solution:

    def solve(self, N: int, M: int) -> int:

        mod = 10**9+7
        INT_MAX = 10**7

        # calculate {m+n}C{n}

        def egcd(a, b):
            if a == 0:
                return b, 0, 1
            else:
                g, y, x = egcd(b % a, a)
                return g, x - (b // a) * y, y

        def modinv(a, m):
            g, x, y = egcd(a, m)
            if g != 1:
                raise Exception('modular inverse does not exist')
            else:
                return x % m

        def combination(n: int, r: int, mod: int = 10**9+7) -> int:
            r = min(r, n-r)
            res = 1
            for i in range(r):
                res = res * (n-i) * modinv(i+1, mod) % mod
            return res

        # prime list

        isPrime = [True] * (INT_MAX + 1)
        isPrime[0], isPrime[1] = False, False
        primes = []

        for i in range(2, len(isPrime)):
            if isPrime[i] == True:
                primes.append(i)
                for j in range(2 * i, len(isPrime), i):
                    isPrime[j] = False

        # solve

        m = M
        answer = 1
        factors = {}
        while m > 1:
            for p in primes:
                factors[p] = 0

                while m % p == 0:
                    m //= p
                    factors[p] += 1

                if factors[p] > 0:
                    answer *= combination(N + factors[p] - 1, N - 1, mod=mod)
                    answer %= mod

        return answer


if __name__ == '__main__':

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

    # solve
    solution = Solution()
    print(solution.solve(N, M))

Submission status: Time Limit Exceeded

Solution code:
class Solution:

    def solve(self, N: int, M: int) -> int:

        mod = 10**9+7
        INT_MAX = 10**6

        # calculate {m+n}C{n}

        def egcd(a, b):
            if a == 0:
                return b, 0, 1
            else:
                g, y, x = egcd(b % a, a)
                return g, x - (b // a) * y, y

        def modinv(a, m):
            g, x, y = egcd(a, m)
            if g != 1:
                raise Exception('modular inverse does not exist')
            else:
                return x % m

        def combination(n: int, r: int, mod: int = 10**9+7) -> int:
            r = min(r, n-r)
            res = 1
            for i in range(r):
                res = res * (n-i) * modinv(i+1, mod) % mod
            return res

        # prime list

        isPrime = [True] * (INT_MAX + 1)
        isPrime[0], isPrime[1] = False, False
        primes = []

        for i in range(2, len(isPrime)):
            if isPrime[i] == True:
                primes.append(i)
                for j in range(2 * i, len(isPrime), i):
                    isPrime[j] = False

        # solve

        m = M
        answer = 1
        factors = {}
        while m > 1:
            for p in primes:
                factors[p] = 0

                while m % p == 0:
                    m //= p
                    factors[p] += 1

                if factors[p] > 0:
                    answer *= combination(N + factors[p] - 1, N - 1, mod=mod)
                    answer %= mod

        return answer


if __name__ == '__main__':

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

    # solve
    solution = Solution()
    print(solution.solve(N, M))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n,m=map(int,input().split())
mod=10**9+7
kaidan=[1]*(2*10**5+1)
gyaku=[1]*(2*10**5+1)

for i in range(1, 2*10**5):
    kaidan[i]=i*kaidan[i-1] % mod
    gyaku[i]=pow(kaidan[i],mod-2,mod)
def comb(a,b):
    if a>0 and b>0 and a-b>0:
        return (kaidan[a] * gyaku[b]*gyaku[a-b])%mod
    elif a==0 or b==0 or a-b==0:
        return 1
    else:
        return 0

soin=defaultdict(int)
while m>=2:
    for i in range(2,int(n**.5)+5):
        while m%i==0 and m!=0:
            m//=i
            soin[i]+=1
            if m==1:
                break
                
L=list(soin.values())
ans=1
for l in L:
    ans*=comb(l+n-1,l)
    ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from scipy.misc import comb


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

# 逆元
# a^{-1} mod を計算する
def mod_inv(a, m):
    return pow(a, m-2, m) % m


def combination(a, b):
    if b > a - b:
        return combination(a, a - b)

    # 10C3 = (10*9*8)/(3*2*1)
    # 10*9*8 -> ans_mul
    # 3*2*1 -> ans_div
    ans_mul = 1
    ans_div = 1
    for i in range(b):
        ans_mul *= a - i
        ans_div *= i + 1
        ans_mul %= MOD
        ans_div %= MOD
    # ans_mul / ans_div をやりたい
    # ans_div の逆元を使って求める
    ans = ans_mul * mod_inv(ans_div, MOD)
    return ans


# M を素因数分解
m_nokori = M
ans = 1
for i in range(2, M+1):
    if m_nokori == 1:
        break
    cnt = 0
    while m_nokori % i == 0:
        cnt += 1
        m_nokori //= i
    # cnt が 2^X とか 3^X の X の部分
    ans *= comb(N+cnt-1, N-1, exact=True)
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

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

# 逆元
# a^{-1} mod を計算する
def mod_inv(a, m):
    return pow(a, m-2, m) % m


def combination(a, b):
    if b > a - b:
        return combination(a, a - b)

    # 10C3 = (10*9*8)/(3*2*1)
    # 10*9*8 -> ans_mul
    # 3*2*1 -> ans_div
    ans_mul = 1
    ans_div = 1
    for i in range(b):
        ans_mul *= a - i
        ans_div *= i + 1
        ans_mul %= MOD
        ans_div %= MOD
    # ans_mul / ans_div をやりたい
    # ans_div の逆元を使って求める
    ans = ans_mul * mod_inv(ans_div, MOD)
    return ans


# M を素因数分解
m_nokori = M
ans = 1
for i in range(2, M+1):
    if m_nokori == 1:
        break
    cnt = 0
    while m_nokori % i == 0:
        cnt += 1
        m_nokori //= i
    # cnt が 2^X とか 3^X の X の部分
    ans *= combination(N+cnt-1, N-1)
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

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


# 逆元
# a^{-1} mod を計算する
def mod_inv(a, m):
    return pow(a, m-2, m)


def combination(a, b):
    if b > a - b:
        return combination(a, a - b)
    # 10C3 = (10*9*8)/(3*2*1)
    # 10*9*8 -> ans_mul
    # 3*2*1 -> ans_div
    ans_mul = 1
    ans_div = 1
    for i in range(b):
        ans_mul *= a - i
        ans_div *= i + 1
        ans_mul %= MOD
        ans_div %= MOD
    # ans_mul / ans_div をやりたい
    # ans_div の逆元を使って求める
    ans = ans_mul * mod_inv(ans_div, MOD)
    return ans


# M を素因数分解
m_nokori = M
ans = 1
for i in range(2, M+1):
    if m_nokori == 1:
        break
    cnt = 0
    while m_nokori % i == 0:
        cnt += 1
        m_nokori //= i
    # cnt が 2^X とか 3^X の X の部分
    ans *= combination(N+cnt-1, N-1)
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
mod = int(1e+9 + 7)
a = mod - 2
ax = []
while a != 0:
  ax = [a%2] + ax[:]
  a //= 2
def inved(x):
  y = 1
  for i in range(len(ax)):
    if ax[i] == 1:
      y *= x
      y %= mod
    if i != len(ax) - 1:
      y *= y
      y %= mod
  return y

p, n = 2, M
L = []
while n != 1:
  i = 0
  while n % p == 0:
    n //= p
    i += 1
  if i != 0:
    L.append(i)
  p += 1
  if L == [] and p > int(M**(1/2))+1:
    L.append(1)
    break
if M == 1:
  print(1)
else:
  prod = 1
  mm = max(L)
  fact = [1]
  for i in range(N + mm - 1):
    fact.append((fact[i] * (i + 1)) % mod)
  invf = inved(fact[N - 1])
  for i in L:
    pad = (fact[N - 1 + i] * inved(fact[i]) * invf) % mod
    prod *= pad
    prod %= mod
  print(prod)

Submission status: Time Limit Exceeded

Solution code:

N,M=[int(x) for x in str(input()).split()]
lim=int(M**0.5)+10000000

prime_sieve=[1 for i in range(lim)]


prime_sieve[0]=0
prime_sieve[1]=0

prime=[]
count=[]
for i in range(2,lim):
  if prime_sieve[i]==1:
    prime.append(i)
    count.append(0)
    for j in range(2,(lim-1)//i+1):
      prime_sieve[i*j]=0

for i in range(len(prime)):
  while M%prime[i]==0:
    count[i]+=1
    M=M//prime[i]
  if M==1:
    break


num=10**9+7
x=1
factorial=[1]
for i in range(1,2*10**5+1):
  x=(i*x)%num
  factorial.append(x)
 
rfactorial=[]
for i in factorial:
  rfactorial.append(pow(i,num-2,num))
 

def c(n,k):
  return (((factorial[n]*rfactorial[k])%num)*rfactorial[n-k])%num


ans=1
for i in range(len(prime)):
  ans=(ans*c(N-1+count[i],count[i]))%num
print(ans)