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:
def prime(M_0):
    M = M_0
    lst = []
    i = 2
    while M != 1:
        if M % i == 0:
            lst.append(i)
            M = M // i
        elif len(lst) == 0 and i ** 2 > M_0:
            return [M_0]
        else:
            i += 1
    return lst


def counter(lst):
    dic = {}
    for i in lst:
        if i not in dic:
            dic[i] = 1
        else:
            dic[i] += 1
    return dic


def cmb(n, r, R):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k]) % R

    return result


R = 10 ** 9 + 7
N, M = map(int, input().split())
val = 1
for i in counter(prime(M)).values():
    val *= cmb(N + i - 1, i, R)
    if val >= R:
        val = val % R

print(val)

Submission status: Time Limit Exceeded

Solution code:
def prime(M):
    lst = []
    i = 2
    while M != 1:
        if M % i == 0:
            lst.append(i)
            M = M // i
        else:
            i += 1
    return lst


def counter(lst):
    dic = {}
    for i in lst:
        if i not in dic:
            dic[i] = 1
        else:
            dic[i] += 1
    return dic


def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result


N, M = map(int, input().split())
val = 1
for i in counter(prime(M)).values():
    val = ((val * cmb(N + i - 1, i)) % (10 ** 9 + 7))
    
print(val)

Submission status: Time Limit Exceeded

Solution code:
def prime(M):
    lst = []
    i = 2
    while M != 1:
        if M % i == 0:
            lst.append(i)
            M = M // i
        else:
            i += 1
    return lst


def counter(lst):
    dic = {}
    for i in lst:
        if i not in dic:
            dic[i] = 1
        else:
            dic[i] += 1
    return dic


def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result


N, M = map(int, input().split())
val = 1
for i in counter(prime(M)).values():
    val *= cmb(N + i - 1, i)
    if val >= 10 * 9 + 7:
        val = val % (10 ** 9 + 7)

print(val)

Submission status: Time Limit Exceeded

Solution code:
#How many ways M=a1*a2*...*aN ex)N=2,M=6 a={1,6},{2,3},{3,2},{6,1}
import math
n,m=map(int,input().split())
factor=[]
c=0
mod=10**9+7

#Prime Factorization [number,times]
while m%2 == 0:
    m//=2
    c+=1
if c != 0:
    factor.append([2,c])
#Alternate
for i in range(3,m+1,2):
    c=0
    while m%i == 0:
        m//=i
        c+=1
    if c != 0:
        #print(i,c)
        factor.append([i,c])
    if m == 1:
        break
    if i*i>=m:  # m is prime
        factor.append([m,1])
        break
        
#print(factor)

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

def funcount(length,rest):
    a=0
    if length==1:
        #print(rest)
        return 1
    elif rest <= 1:
        #print("not",rest)
        return 0
    else:
        for i in range(1,rest):
            #print(i,end=" ")
            a+=funcount(length-1,rest-i)
        return a


way=1
for f in factor:
    sum=0
    for k in range(1,f[1]+1):
        sum+=funcount(k,f[1])*C(n,k)
    way=(way*sum)%mod
    
print(way%mod)

Submission status: Time Limit Exceeded

Solution code:
#How many ways M=a1*a2*...*aN ex)N=2,M=6 a={1,6},{2,3},{3,2},{6,1}
import math
n,m=map(int,input().split())
factor=[]
c=0
mod=10**9+7

#Prime Factorization [number,times]
while m%2 == 0:
    m//=2
    c+=1
if c != 0:
    factor.append([2,c])
#Alternate
for i in range(3,m+1,2):
    c=0
    while m%i == 0:
        m//=i
        c+=1
    if c != 0:
        factor.append([i,c])


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

def funcount(length,rest):
    a=0
    if length==1:
        #print(rest)
        return 1
    elif rest <= 1:
        #print("not",rest)
        return 0
    else:
        for i in range(1,rest):
            #print(i,end=" ")
            a+=funcount(length-1,rest-i)
        return a


way=1
for f in factor:
    sum=0
    for k in range(1,f[1]+1):
        sum+=funcount(k,f[1])*C(n,k)
    way*=sum
    
print(way%mod)

Submission status: Time Limit Exceeded

Solution code:
import math

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

R = 10**9 + 7

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

decomposition = []
i = 2
while i * i <= M:
    if M % i == 0:
        decomposition.append(0)
        while M % i ==0:
            decomposition[-1] = decomposition[-1] + 1
            M = M//i
    i = i + 1
if M > 1:
    decomposition.append(1)

H = [ combination(N+k-1,k) % R for k in decomposition]
r = 1
for h in H:
    r = (r*h) % R

print(r)

Submission status: Time Limit Exceeded

Solution code:
import math


def combinations_with_replacement_count(n, r):
    return math.factorial(n + r - 1) // (math.factorial(n - 1) * math.factorial(r))


nm = list(map(int, input().split()))
n = nm[0]
m = nm[1]
fact = {}
i = 2
while i * i <= m:
    while m % i == 0:
        m = m // i
        if i in fact:
            fact[i] += 1
        else:
            fact[i] = 1
    i += 1
if m > 1:
    fact[m] = 1
j = 2
ans = 1
for k in fact:
    ans = ans * combinations_with_replacement_count(n, fact[k])
print(ans % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
import math


def combinations_with_replacement_count(n, r):
    return math.factorial(n + r - 1) // (math.factorial(n - 1) * math.factorial(r))


nm = list(map(int, input().split()))
n = nm[0]
m = nm[1]
fact = {}
i = 2
while m != 1 :
    while m % i == 0:
        m = m // i
        if i in fact:
            fact[i] += 1
        else:
            fact[i] = 1
    i += 1
j = 2
ans = 1
for k in fact:
    ans = ans * combinations_with_replacement_count(n, fact[k])
print(ans % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
def com(n,m):
    if(n-m < m):
        m=n-m
    result=1
    mylist=[i for i in range(1,m+1)]
    j=1
    for i in range(1,m+1):
        result*=(n+1-i)
        if(j<m):
            while(result%mylist[j]==0):
                result//=mylist[j]
                j+=1
                if(j>=m):
                    break
    return result

def yakusuu(i,m):
    _i=i
    while(i*2<=m):
        if(m%i==0):
            return i
        else:
            i+=1
    for j in range(_i-1,0,-1):
        if(m%j==0):
            break
    return m//j
    

N,M=map(int,input().split())
soinsuubunkai={}
tmp=2
i=2
_M=M
while(tmp <=M):
    tmp=yakusuu(tmp,M)

    if(tmp in soinsuubunkai):
        soinsuubunkai[tmp]+=1
    else:
        soinsuubunkai[tmp]=1
    M//=tmp
    if(M==1):
        break


tmp=1
for k in list(soinsuubunkai.values()):
    tmp*=com(k+N-1,k)
    tmp%=10**9+7
print(tmp)

Submission status: Time Limit Exceeded

Solution code:
def com(n,m):
    if(n-m < m):
        m=n-m
    result=1
    mylist=[i for i in range(1,m+1)]
    j=1
    for i in range(1,m+1):
        result*=(n+1-i)
        if(j<m):
            while(result%mylist[j]==0):
                result//=mylist[j]
                j+=1
                if(j>=m):
                    break
    return result

N,M=map(int,input().split())
soinsuubunkai=[]
tmp=1
i=2
flag=0
while(i <=M):
    if(M%i==0):
        if(flag==0):
            soinsuubunkai.append(1)
        else:
            soinsuubunkai[-1]+=1
        M//=i
        flag=1
    else:
        i+=1
        flag=0

tmp=1
for k in soinsuubunkai:
    tmp*=com(k+N-1,k)
    tmp%=10**9+7
print(tmp)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


def main():
    """
    1 <= N <= 10^5
    1 <= M <= 10^9

    正整数 N, M
    a1 * a2 * ... * aN = M となる長さNの数列a
    何通りあるか
    数列A1-ai != 数列A2-ai
    """
    N, M = map(int, input().split())

    ans = editorial(N, M)
    print(ans)


def factorize(N):
    """素因数分解

    TODO: もっと速い方法
    素因数がある場合は範囲をsqrtで狭められるが、ない場合愚直に探してしまう
    N以下の素数を見つけて、それだけで対応すれば速いはず
    """
    import math
    factors = []
    while True:
        if N % 2 == 0:
            factors.append(2)
            N //= 2
        else:
            break
    m = int(math.sqrt(N))
    i = 3
    while i <= m:
        add = False
        while True:
            if N % i == 0:
                factors.append(i)
                N //= i
                add = True
            else:
                break
        if add:
            m = int(math.sqrt(N))
        i += 2
    if N > 1:
        factors.append(N)
    return factors


def f(N, M):
    """
    M を素因数分解すると約数とそれらの個数がわかる
    それらの組合せを制約を満たすようにする
    1 * M, M * 1 をわすれないこと:
        1 * 1 * 1 * M もOK

    3 12
        1,1,12: 3P3 / 2!
        2,2,3:  3P3 / 2!
        3,4,1:  3P3
        6,2,1:  3P3

    http://sucrose.hatenablog.com/entry/2014/10/10/235805
    """
    ans = 0
    m = 10 ** 9 + 7
    factors = factorize(M)
    c = Counter(factors)
    print(c)
    return ans


def editorial(N, M):
    i = 2
    rest_M = M
    ans = 1
    mod = 10 ** 9 + 7
    while i ** 2 <= rest_M:
        div_count = 0
        while rest_M % i == 0:
            div_count += 1

        if div_count > 0:
            # N - 1 == div_count
            ans *= calc_comb(N + div_count + 1, N - 1)
            ans %= mod

    if rest_M != 1:
        ans *= calc_comb(N + 1 + 1, N - 1)
        ans %= mod

    return ans


def calc_comb(n, r, mod=10 ** 9 + 7):
    if r > n - r:
        return calc_comb(n, n - r)

    ans_mul = 1
    ans_div = 1

    for i in range():
        # n! / (n - r)!
        ans_mul = ans_mul * (n - i) % mod
        # r!
        ans_div = ans_div * (i + 1) % mod

    # k^(-1) ≡ k^(n-2) (mod n)
    return ans_mul * mod_pow(ans_div, mod - 2) % mod


def mod_pow(a, p, mod=10 ** 9 + 7):
    if p == 0:
        return 1

    if p % 2 == 0:
        half_p = p // 2
        half = mod_pow(a, half_p)
        return half ** 2 % mod
    else:
        return a * mod_pow(a, p - 1) % mod


def mod_pow_bit(a, p, mod=10 ** 9 + 7):
    """
    http://keita-matsushita.hatenablog.com/entry/2016/12/05/184011
    """
    ans = 1
    while p > 0:
        if (p & 1) == 1:
            ans = ans * a % mod

        a = a ** 2 % mod
        p >>= 1

    return ans


def ref(N, M):
    """
    https://mathtrain.jp/tyohukuc
        n 種類のものから重複を許して r 個選ぶ場合の数
        n H r = (n+r−1) C r

    3 12 の例で示せているのに、重複組合せという言葉が頭に浮かばなかった

    解説動画より
    modの世界における逆元?
        重複組合せ
            フェルマーの小定理
                ref: http://keita-matsushita.hatenablog.com/entry/2016/12/05/184011
            階乗と階乗逆元
        拡張ユークリッド互除法
            今回は出番なし
    """
    def create_tables(N, MOD):
        """
        http://drken1215.hatenablog.com/entry/2018/06/08/210000
        """
        fact_mod = [0] * (N + 1)
        simod = [0] * (N + 1)
        fact_inv_mod = [0] * (N + 1)

        fact_mod[0] = fact_mod[1] = 1
        simod[0] = simod[1] = 1
        fact_inv_mod[0] = fact_inv_mod[1] = 1

        for i in range(2, N + 1):
            fact_mod[i] = (fact_mod[i - 1] * i) % MOD
            simod[i] = MOD - simod[MOD % i] * (MOD // i) % MOD
            fact_inv_mod[i] = (fact_inv_mod[i - 1] * simod[i]) % MOD
            # inv 配列が確実に不要な場面 とは？ (ここでのsimod)
            # inv[n] を逆元計算によって計算しておく
            # finv[i-1] = finv[i] * i % MOD によって finv 配列を後ろから計算していく

        return fact_mod, fact_inv_mod

    def create_fact_mod(N, MOD):
        fact_mod = [0] * (N + 1)
        fact_mod[0] = 1
        fact_mod[1] = 1

        # 階乗のテーブル作成, 累積積によって計算量を落としている
        for i in range(2, N + 1):
            fact_mod[i] = (fact_mod[i - 1] * i) % MOD

        return fact_mod

    def create_seq_inv_mod(N, MOD):
        simod = [0] * (N + 1)
        simod[0] = 1  # 0のままでもよい?
        simod[1] = 1

        # 階乗逆元のテーブル用に作成
        for i in range(2, N + 1):
            simod[i] = (MOD - MOD // i) * simod[MOD % i] % MOD
            # 下記との違いはなにか？
            # simod[i] = MOD - simod[MOD % i] * (MOD // i) % MOD

        return simod

    def create_fact_inv_mod(N, MOD, simod):
        fact_inv_mod = [0] * (N + 1)
        fact_inv_mod[0] = 1
        fact_inv_mod[1] = 1

        # 階乗逆元のテーブル作成
        for i in range(2, N + 1):
            fact_inv_mod[i] = (fact_inv_mod[i - 1] * simod[i]) % MOD

        return fact_inv_mod

    def comb_mod(N, R, fact_mod, fact_inv_mod, MOD):
        """
        組合せ nCr: n! / ((n-r)! * r!)
        上記のmodを逆元を使って表現

        f[n] * f[r] % MOD * f[n-r] % MOD 
        これのために事前にテーブルを作っていた
        """
        return fact_mod[N] * fact_inv_mod[N - R] * fact_inv_mod[R] % MOD

    ans = 1
    m = 10 ** 9 + 7
    factors = factorize(M)
    c = Counter(factors)

    # N + 10 でRE: 重複組合せなのでN以上になるため、約数2が32個あればそうなる
    # https://beta.atcoder.jp/contests/abc110/submissions/3253308
    # http://betrue12.hateblo.jp/entry/2018/09/24/020414
    fact_mod = create_fact_mod(N + 100, m)
    simod = create_seq_inv_mod(N + 100, m)
    fact_inv_mod = create_fact_inv_mod(N + 100, m, simod)

    # 重複組合せ: n! / (a! * (b - a)!)
    # 重複組合せ を 各素因数における組合せ結果の掛け合わせで表現
    for i in c.values():
        ans *= comb_mod(N - 1 + i, i, fact_mod, fact_inv_mod, m)
        ans %= m

    return ans


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, M = list(map(int, input().split()))
MAX_NUM = 10 ** 9 + 7
def func(M):
  res = []
  i, c = 2, 0
  while True:
    if M % i == 0:
      M = M / i
      c+=1
    else:
      if c > 0:
        res.append(c)
        c = 0
      i += 1
      if M==1:
        break
  return res

def conb(n, r):
  N, R = n, r
  for i in range(1, r):
    N *= n-i
    R *= r-i
  return N // R

res = func(M)
ans = 1
for i in res:
  ans = (ans * conb(i+N-1, i)) % MAX_NUM
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
	
N,M = map(int,raw_input().split())

def factorize(n):
	fct = []  # prime factor
	b, e = 2, 0  # base, exponent
	while b * b <= n:
		while n % b == 0:
			n = n / b
			e = e + 1
		if e > 0:
			fct.append((b, e))
		b, e = b + 1, 0
	if n > 1:
		fct.append((n, 1))
	return fct

fct= factorize(M)

ans = 1

for f in fct:
	ans=(ans *(math.factorial(f[1]+N-1)/(math.factorial(f[1])*math.factorial(N-1))))%(10**9+7)

print ans

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import math
mod = 1000000007

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    result = 1
    for i in range(n-r+1, n+1):
        result *= i

    for i in range(1,r+1):
        result //= i

    return result % mod

s=input()
N, M = map(int, s.split())
M1=M
result=1

for i in range(2, M1+1):
    c=0
    while M % i == 0:
        M /= i
        c=c+1
        
    if c>0:
        result =result * cmb(N+c-1,c) % mod

print(result)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
def H(x, y):
    return factorial(x + y - 1) // (factorial(x - 1) * factorial(y))
n, m = list(map(int, input().split()))
p = 2
prime_factorization = []
while p * p <= m:
    count = 0
    while m % p == 0:
        m //= p
        count += 1
    if count > 0:
        prime_factorization.append(count)
    p += 1
if m > 1:
    prime_factorization.append(1)
ans = 1
for r in prime_factorization:
    ans *= H(n, r)
print(ans % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
RC110 D
"""


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

from math import sqrt
from collections import deque
def divisors(x):
    divs = deque()
    sx = int(sqrt(x))
    if x == sx**2:
        divs.append(sx)
        sx = sx-1
    for i in range(sx,0,-1):
        if x%i==0:
            divs.append(i)
            divs.appendleft(x//i)
    return(divs)

mdivs = list(divisors(m))
from collections import defaultdict
divsdict = defaultdict(list)
for d in mdivs:
    divsdict[d] = [dd for dd in mdivs if d%dd==0]

dpdict = defaultdict(int)
for d in mdivs:
    dpdict[d]=0
dpdict[1] = 1


cut = 10**9+7

for i in range(n):
    for d in mdivs:
        dpdict[d] = sum(map(lambda x:dpdict[x],divsdict[d]))%(10**9+7)

print(dpdict[m])

Submission status: Time Limit Exceeded

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
RC110 D
"""


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

from math import sqrt
from collections import deque
def divisors(x):
    divs = deque()
    sx = int(sqrt(x))
    if x == sx**2:
        divs.append(sx)
        sx = sx-1
    for i in range(sx,0,-1):
        if x%i==0:
            divs.append(i)
            divs.appendleft(x//i)
    return(divs)

mdivs = list(divisors(m))
from collections import defaultdict
divsdict = defaultdict(list)
for d in mdivs:
    divsdict[d] = [dd for dd in mdivs if d%dd==0]

dpdict = defaultdict(int)
for d in mdivs:
    dpdict[d]=0
dpdict[1] = 1

cut = 10**9+7

for i in range(n):
    dpdicttmp = dpdict
    for d in mdivs:
        dpdict[d] = sum(map(lambda x:dpdict[x],divsdict[d]))%(10**9+7)

print(dpdict[m])

Submission status: Time Limit Exceeded

Solution code:
import math
mod = 10**9 + 7
n, m = map(int, input().split())
#mの素因数分解
#(prime, power)を要素としてもつ配列を返す関数を作る
def factorize(n):
    fct = []
    b, e = 2, 0
    while b*b <= n:
        while n%b == 0:
            n //= b
            e += 1
        if e > 0:
            fct.append((b, e))
        b += 1
        e = 0
    if n > 1:
        fct.append((n, 1))
    return fct

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

num = factorize(m)
ans = 1
for p in num:
    ans *= (combinations_count(p[1]+n-1, p[1]) % mod)
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import math
def nCr(n,r):
    return (math.factorial(n)) // (math.factorial(r)) // (math.factorial(n-r))
def nHr(n,r):
    return nCr(n+r-1, r-1)
def prime(n): # nまでの素数を列挙
    import math
    num_list = [i + 1 for i in range(2,n,2)]
    list_prime = [2]
    limit = math.sqrt(n)
    if n == 2:
        return list_prime
    else:
        while True:
            p = num_list[0]
            if p >= limit:
                return list_prime + num_list
            list_prime.append(p)
            num_list = [num for num in num_list if num % p != 0]

def primeFactorization(n):
    import math
    list_prime = prime(int(math.sqrt(n)))
    i = 0
    dict_pF = {}
    dict_primeFactorization = {}
    for pri in list_prime:
        dict_pF[pri] = 0
    while True:
        if n == 1:
            for key, value in dict_pF.items():
                if value != 0:
                    dict_primeFactorization[key] = value
            return dict_primeFactorization
        elif i >= len(list_prime):
            dict_pF[n] = 1
            for key, value in dict_pF.items():
                if value != 0:
                    dict_primeFactorization[key] = value
            return dict_primeFactorization
        p = list_prime[i]
        if n % p == 0:
            n //= p
            dict_pF[p] += 1
            continue
        else:
            i += 1

ans = 1
n,m = map(int, input().split())
if m == 1:
    ans = 1
else:
    for factor,degree in primeFactorization(m).items():
        ans *= (nHr(degree,n)) % (10**9+7)

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys
def comb(n, c):
    q, z = 1, 1
    for i in range(c):
        q *= n-i
        z *= i+1
    return q//z

def main():
    n, m = [int(_) for _ in sys.stdin.readline().rstrip().split(' ')]

    z = 2
    pa = []
    while m>1:
        c=0
        if m%z==0:
            c=0
            while m%z==0:
                m//=z
                c+=1
            pa.append(c)
    
        z+=1

    z = 1
    for p in pa:
        z *= comb(p+n-1, p)
    
    print(z%1000000007)



if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import time
import math
import collections

def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table



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

factors = collections.Counter(prime_decomposition(M))
num_pattern = 1;
for exponent in factors.values():
    tmp_num_pattern = math.factorial(exponent + N -1) \
                        // (math.factorial(exponent)*math.factorial(N-1))  
    num_pattern = num_pattern * int(tmp_num_pattern)
    
print(num_pattern%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
def factor_list(n):
    res = []
    i = 2
    while i <= n:
        tmp = 0
        while n % i == 0:
            n = n // i
            tmp += 1
        if tmp > 0:
            res.append((i,tmp))
        i += 1
    return res

def combination(n,k):
    res = 1
    for i in range(n-k+1,n+1):
        res *= i 
    for i in range(1,k+1):
        res = res // i 
    return res
factors = factor_list(m)
count = 1
for num,cnt in factors:
    count *= combination(cnt+n-1,cnt)
print(count % (10**9+7))

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
i=2
s=[]
while 1<m:
  j=0
  while m % (i**(j+1))==0:
    j+=1
  if j:
    m//=i**j
    s+=[j]
  i+=1
a=1
for v in s:
  c = 1
  for i in range(v):
    c = c * (n+i) // (1+i)
  a = a * c % (10**9+7)
print(a)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
i=2
s={}
while 1<m:
  j=0
  while m % (i**(j+1))==0:
    j+=1
  if j:
    m//=i**j
    s[i]=j
  i+=1
a=1
for v in s.values():
  c = 1
  for i in range(v):
    c = c * (n+i) // (1+i)
  a = a * c % (10**9+7)
print(a)

Submission status: Time Limit Exceeded

Solution code:
import math
import collections
import scipy.misc as scm

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

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

a = [i for i in range(2,40000)]
p = []

while a[0] <= int(40000**0.5)+1:
    p.append(a[0])
    k = 1
    size = len(a)
    while k < size:
        if a[k]%a[0] == 0:
            a.pop(k)
            size += -1
        else:
            k += 1
    a.pop(0)
p = p+a


element = []
while m != 1:
    i = 0
    while p[i] <= int(m**0.5)+10:
        if m%p[i] == 0:
            element.append(p[i])
            m = m//p[i]
        i += 1
    if i == int(m**0.5)+9:
        break

data = collections.Counter(element)

ans = 1
for i in data:
    ans = (ans*scm.comb(data[i]+n-1,data[i],1))%1000000007
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import collections

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

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

a = [i for i in range(2,40000)]
p = []

while a[0] <= int(40000**0.5)+1:
    p.append(a[0])
    k = 1
    size = len(a)
    while k < size:
        if a[k]%a[0] == 0:
            a.pop(k)
            size += -1
        else:
            k += 1
    a.pop(0)
p = p+a


element = []
while m != 1:
    i = 0
    while p[i] <= int(m**0.5)+10:
        if m%p[i] == 0:
            element.append(p[i])
            m = m//p[i]
        i += 1
    if i == int(m**0.5)+9:
        break

data = collections.Counter(element)

ans = 1
for i in data:
    ans = (ans*combination(data[i]+n-1,data[i]))%1000000007
print(ans)

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7


def prime_counter(n):
    ret = []
    for i in range(2, int(n / 2) + 2):
        count = 0
        while n % i == 0:
            n /= i
            count += 1
        if 0 < count:
            ret.append(count)
        if n == 1:
            break
    if 1 < n:
        ret.append(1)
    return ret


def comb(n, r):
    r = min(r, n - r)
    if r == 0:
        return 1
    elif r == 1:
        return n
    return (n % MOD) * pow(r, MOD - 2, MOD) * comb(n - 1, r - 1) % MOD


factnum = prime_counter(M)
ans = 1

for p in factnum:
    ans *= comb(p + N - 1, p)

ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7


def prime_counter(n):
    ret = []
    for i in range(2, int(n / 2) + 2):
        count = 0
        while n % i == 0:
            n /= i
            count += 1
        if 0 < count:
            ret.append(count)
        if n == 1:
            break
    if 1 < n:
        ret.append(1)
    return ret


def comb(n, r):
    r = min(r, n - r)
    if r == 0:
        return 1
    elif r == 1:
        return n
    return (n % MOD) * pow(r, MOD - 2, MOD) * comb(n - 1, r - 1) % MOD


factnum = prime_counter(M)
ans = 1

for i, p in enumerate(factnum):
    ans *= comb(p + N - 1, p)

ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7


def prime_counter(n):
    ret = []
    for i in range(2, int(n / 2) + 1):
        count = 0
        while n % i == 0:
            n /= i
            count += 1
        if 0 < count:
            ret.append(count)
        if n == 1:
            break
    if 1 < n:
        ret.append(1)
    return ret


def comb(n, r):
    r = min(r, n - r)
    if r == 0:
        return 1
    elif r == 1:
        return n
    return (n % MOD) * pow(r, MOD - 2, MOD) * comb(n - 1, r - 1) % MOD


factnum = prime_counter(M)
ans = 1

for i, p in enumerate(factnum):
    ans *= comb(p + N - 1, p)

ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split(" "))
fact = {}
for i in range(2,M):
    while (M%i == 0):
        if i in fact:
            fact[i] += 1
        else:
            fact[i] = 1
        M //= i
    if (M == 1):
        break


MOD = 10**9+7

def nCr_mod(n,r,mod): #nCrmod
    r = min(n-r,r)
    v = 1
    for i in range(r):
        v = (v * ((n-i)%mod) * pow((i+1),mod-2,mod)) % mod
    return v

ans = 1
for key,item in fact.items():
    ans *= nCr_mod((item + (N) - 1),N-1,MOD)
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

MOD = 1000000007
MAX = 2000000010


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


def count_div(n):
    fact = []
    count = 0
    i = 2
    while (n != 1):
        while (n % i == 0):
            n = int(n / i)
            count += 1
        fact.append(count)
        count = 0
        i += 1
    return fact


def main():
    N, M = map(int, input().split())
    ans = 1
    fact = count_div(M)
    for i, p in enumerate(fact):
        ans *= comb(p + N - 1, p)
    return ans % MOD


print(main())

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)

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

MOD = 10 ** 9 + 7

if m == 1:
    print('1')
    exit()

factor = []
temp = 0
x = 2
while m > 1:
    if m % x == 0:
        m //= x
        temp += 1
    elif temp > 0:
        factor.append(temp)
        temp = 0
        x += 1
    else:
        x += 1
factor.append(temp)

nCr = {}
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n;
    if (n, r) in nCr: return nCr[(n, r)]

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p;
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    nCr[(n, r)] = result
    return result;

ans = 1
for x in factor:
    ans *= cmb(x + n - 1, n - 1)
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7

if m == 1:
    print('1')
    exit()

factor = []
temp = 0
x = 2
while m > 1:
    if m % x == 0:
        m //= x
        temp += 1
    elif temp > 0:
        factor.append(temp)
        temp = 0
        x += 1
    else:
        x += 1
factor.append(temp)

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n;

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p;
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result;

ans = 1
for x in factor:
    ans *= cmb(x + n - 1, n - 1)
    ans %= MOD

print(ans)