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 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
            rest_M //= i

        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(r):
        # 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: Wrong Answer

Solution code:
import math

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

dict1 = {}

def yakusuu(m):
    if int(m) != 1:
        """
        if m % 2 == 0:
            if 2 not in dict1.keys():
                dict1[2] = 0
            dict1[2] += 1
            yakusuu(m/2)
        elif m % 3 == 0:
            if 3 not in dict1.keys():
                dict1[3] = 0
            dict1[3] += 1
            yakusuu(m/3)
        elif m % 5 == 0:
            if 5 not in dict1.keys():
                dict1[5] = 0
            dict1[5] += 1
            yakusuu(m/5)
        else:
        """
        flag = True
        for i in range(2,int(math.sqrt(m)+1)):
            if m % i == 0:
                if i not in dict1.keys():
                    dict1[i] = 0
                dict1[i] += 1
                yakusuu(m/i)
                flag = False
                break
        if flag == True:
            m = int(m)
            if m not in dict1.keys():
                dict1[m] = 0
            dict1[m] += 1

yakusuu(m)
#print(dict1)

count = 1

for i in dict1.values():
#    print(i)
    a = int(math.factorial(n+i-1) / (math.factorial(n-1) * math.factorial(i)))
    count *= a
#    print(a)

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

Submission status: Wrong Answer

Solution code:
import math

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

dict1 = {}

def yakusuu(m):
    if int(m) != 1:
        """
        if m % 2 == 0:
            if 2 not in dict1.keys():
                dict1[2] = 0
            dict1[2] += 1
            yakusuu(m/2)
        elif m % 3 == 0:
            if 3 not in dict1.keys():
                dict1[3] = 0
            dict1[3] += 1
            yakusuu(m/3)
        elif m % 5 == 0:
            if 5 not in dict1.keys():
                dict1[5] = 0
            dict1[5] += 1
            yakusuu(m/5)
        else:
        """
        flag = True
        for i in range(2,int(math.sqrt(m)+1)):
            if m % i == 0:
                if i not in dict1.keys():
                    dict1[i] = 0
                dict1[i] += 1
                yakusuu(m/i)
                flag = False
                break
        if flag == True:
            m = int(m)
            if m not in dict1.keys():
                dict1[m] = 0
            dict1[m] += 1

yakusuu(m)
print(dict1)

count = 1

for i in dict1.values():
    print(i)
    a = int(math.factorial(n+i-1) / (math.factorial(n-1) * math.factorial(i)))
    count *= a
    print(a)

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

Submission status: Wrong Answer

Solution code:
N, M = list(map(int, input().split()))
MAX_NUM = 10 ** 9 + 7
def func(M):
  res = []
  i, c = 2, 0
  if M==1:
    return [1]
  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: Wrong Answer

Solution code:
import numpy as np
import math
N,M = map(int, input().split())

dict_p = {}
m=M

def factoring(n):
    dict_p = {}
    m = n
    for i in range(2,round(n**(1/2)) + 2):
        while m%i == 0:
            if i not in dict_p.keys():
                dict_p[i] = 1
            else:
                dict_p[i] += 1
            m = m//i
    return dict_p

dict_p = factoring(M)
#c = np.zeros((N,len(dict_p))
ans = 1
for p in dict_p:
    ans = ans * (math.factorial(dict_p[p] + N-1)//(math.factorial(dict_p[p])*math.factorial(N-1)))
    ans = ans % (10**9+7)
print(int(ans))

Submission status: Wrong Answer

Solution code:
# ABC 110 D
# Math
import math, collections
N, M = map(int,input().split())
MOD = 7+10**9

# prime factorization
Q = []
k = 2
while k < M:
    if M%k == 0:
        Q.append(k)
        M //= k
    else:
        k += 1
Q.append(k)

R = collections.Counter(Q)

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

ans = 1
for f in R:
    ans *= nCr(N+R[f]-1,R[f])
    ans %= MOD
print(ans)

Submission status: Wrong Answer

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

def isprime(n):
    for i in range(2, int(math.sqrt(n))+2):
        if n%i== 0:
            return False
    return True

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

if isprime(M):
    result = N
else:
    for i in range(2, int(math.sqrt(M))+2):
        c=0
        while M % i == 0:
            M /= i
            c=c+1
            
        if c>0:
            result =result * cmb(N+c-1,c) % mod

if M>0:
    result =result * M % mod

print(result)

Submission status: Wrong Answer

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

def isprime(n):
    for i in range(2, int(math.sqrt(n))+2):
        if n%i== 0:
            return False
    return True

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

if isprime(M):
    result = N
else:
    for i in range(2, int(math.sqrt(M))+2):
        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: Wrong Answer

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

def isprime(n):
    for i in range(2, int(math.sqrt(n))+2):
        if n%i== 0:
            return False
    return True

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

if isprime(M):
    result = N
else:
    for i in range(2, int(math.sqrt(M1))+2):
        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: Wrong Answer

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

def isprime(n):
    for i in range(2, int(math.sqrt(n))+2):
        if n%i== 0:
            return False
    return True

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

if isprime(M):
    result = N
else:
    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: Wrong Answer

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, int(math.sqrt(M1)) + 2):
    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: Wrong Answer

Solution code:
from collections import Counter as c
from scipy.misc import comb
from functools import reduce

def f(n):
  d,i=c(),2
  while i*i<=n:
    while n%i==0:
      n//=i
      d[i]+=1
    i += 1
  if n:d[n]+=1
  return d.values()

n,m=map(int,input().split())
mod=10**9+7
print(reduce(lambda x,y:x*y%mod,map(lambda x:comb(x+n-1,x,exact=True),f(m)))%mod)

Submission status: Wrong Answer

Solution code:
from collections import Counter as c
from scipy.misc import comb
from functools import reduce

def f(n):
  d=c()
  for i in range(2,1+int(n**0.5)):
    while n%i==0:
      d[i]+=1
      n//=i
  if n:d[n]+=1
  return d.values()

n,m=map(int,input().split())
mod=10**9+7
print(reduce(lambda x,y:x*y%mod,map(lambda x:comb(x+n-1,x,exact=True),f(m)))%mod)

Submission status: Wrong Answer

Solution code:
from collections import Counter as c
from scipy.misc import comb
from functools import reduce

def f(n):
  d=c()
  for i in range(2,1+int(n**0.5)):
    while n%i==0:
      d[i]+=1
      n/=i
  if n:d[n]+=1
  return d.values()

n,m=map(int,input().split())
mod=10**9+7
print(reduce(lambda x,y:x*y%mod,map(lambda x:comb(x+n-1,x,exact=True),f(m)))%mod)

Submission status: Wrong Answer

Solution code:
from collections import Counter as c
from math import factorial as fac
from functools import reduce

def f(n):
  d=c()
  for i in range(2,1+int(n**0.5)):
    while n%i==0:
      d[i]+=1
      n/=i
  if n:d[n]+=1
  return d.values()

def comb(n,r):
  return (fac(n)//fac(r)//fac(n-r))%mod

n,m=map(int,input().split())
mod=10**9+7
g=lambda x:comb(x+n-1,x)
h=lambda x,y:x*y%mod
print(reduce(h,map(g,f(m)))%mod)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import math
N,M=map(int,input().split())
dd=defaultdict(int)
m=M
mod=10**9+7
for i in range(2,int(math.sqrt(M))+1):
    s=0
    while m%i==0 and m>1:
        m=m//i
        s+=1
    if s>0:
        dd[i]=s
def f(n,k):
    a=1
    for i in range(1,k+1):
        a=a*(n-i+1)
        a%=mod
        a*=pow(i,mod-2,mod)
        a%=mod
    return a
ans=1
for l,t in dd.items():
    ans*=f(N-1+t,t)
    ans%=mod
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N,M=map(int,input().split())
dd=defaultdict(int)
m=M
mod=10**9+7
for i in range(2,10**5):
    s=0
    while m%i==0 and m>1:
        m=m//i
        s+=1
    if s>0:
        dd[i]=s
def f(n,k):
    a=1
    for i in range(1,k+1):
        a=a*(n-i+1)
        a%=mod
        a*=pow(i,mod-2,mod)
        a%=mod
    return a
ans=1
for l,t in dd.items():
    ans*=f(N-1+t,t)
    ans%=mod
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N,M=map(int,input().split())
dd=defaultdict(int)
m=M
mod=10**9+7
for i in range(2,10**5):
    s=0
    while m%i==0 and m>1:
        m=m//i
        s+=1
    if s>0:
        dd[i]=s
def f(n,k):
    a=1
    for i in range(1,k+1):
        a*=n-i+1
        a%=mod
        a*=pow(i,mod-2,mod)
        a%=mod
    return a
ans=1
for s,t in dd.items():
    ans*=f(N-1+t,t)
    ans%=mod
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N,M=map(int,input().split())
dd=defaultdict(int)
m=M
mod=10**9+7
for i in range(2,10**5):
    s=0
    while m%i==0:
        m=m//i
        s+=1
    if s>0:
        dd[i]=s
def f(n,k):
    a=1
    for i in range(1,k+1):
        a*=n-i+1
        a%=mod
        a*=pow(i,mod-2,mod)
        a%=mod
    return a
ans=1
for s,t in dd.items():
    ans*=f(N-1+t,t)
    ans%=mod
print(ans)

Submission status: Wrong Answer

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

print(dpdict)
print(mdivs)

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

Solution code:
def prime_factorization(number):
    l = []
    if number == 1:
        return l
    for i in range(2, int(number ** 0.5) + 2):
        count = 0
        while number % i == 0:
            count += 1
            number //= i
        if count != 0:
            l.append(count)
    if not l:
        l.append(1)        
    return l

def factorial(n):
    if n <= 1:
        return 1
    ans = 1
    for i in range(2, n+1):
        ans *= i
    return ans

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

if __name__ == '__main__':
    mod = 10**9+7
    n, m = map(int, input().split())
    a = prime_factorization(m)
    answer = 1
    for x in a:
        answer *= comb(x+n-1, x)
        answer %= mod
    print(answer)

Submission status: Wrong Answer

Solution code:
def prime_factorization(number):
    l = []
    if number == 1:
        return l
    for i in range(2, int(number ** 0.5) + 2):
        count = 0
        while number % i == 0:
            count += 1
            number //= i
        if count != 0:
            l.append(count)
    return l

def factorial(n):
    if n <= 1:
        return 1
    ans = 1
    for i in range(2, n+1):
        ans *= i
    return ans

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

if __name__ == '__main__':
    mod = 10**9 + 7
    n, m = map(int, input().split())
    a = prime_factorization(m)
    answer = 1
    for x in a:
        answer *= comb(x+n-1, x)
        answer %= mod
    print(answer)

Submission status: Wrong Answer

Solution code:
def prime_factorization(number):
    l = []
    for i in range(2, int(number ** 0.5) + 2):
        count = 0
        while number % i == 0:
            count += 1
            number //= i
        if count != 0:
            l.append(count)
    return l

def factorial(n):
    ans = 1
    for i in range(2, n+1):
        ans *= i
    return ans

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

if __name__ == '__main__':
    mod = 10**9 + 7
    n, m = map(int, input().split())
    a = prime_factorization(m)
    answer = 1
    for x in a:
        answer *= comb(x+n-1, x)
        answer %= mod
    print(answer)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
n,m=map(int,input().split())
l={}
p=2

while m>=p*p:
    if m%p==0:
        if not p in l.keys():
            l[p]=0
        l[p]+=1
        m//=p
    else:
        p+=1
if not m in l.keys():
    l[m]=0
l[m]+=1

ans=1
for p,q in l.items():
    for i in range(q):
        ans*=n+i
    for i in range(q):
        ans//=i+1

print(ans%1000000007)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
n,m=map(int,input().split())
l={}
p=2

while m>=p*p:
    if m%p==0:
        if not p in l.keys():
            l[p]=0
        l[p]+=1
        m/=p
    else:
        p+=1
if not m in l.keys():
    l[m]=0
l[m]+=1

ans=1
for p,q in l.items():
    for i in range(q):
        ans*=n+i
    for i in range(q):
        ans//=i+1

print(ans%1000000007)

Submission status: Wrong Answer

Solution code:

import time
import collections
import scipy.misc

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))
t_elps = time.time()
#print(f"{t_elps - t_strt} [sec]")
num_pattern = 1;

for exponent in factors.values():
    tmp_num_pattern = scipy.misc.comb(exponent + N -1, N-1, exact = True) 
    num_pattern = num_pattern * int(tmp_num_pattern)

Submission status: Wrong Answer

Solution code:
import math

# import time


def get_primes(n):
    primes = []
    checks = [True for _ in range(int(math.sqrt(n)) + 1)]
    checks[0] = checks[1] = False
    for i in range(2, len(checks)):
        if checks[i]:
            primes.append(i)
            tmp = 0
            while i + tmp * i < len(checks):
                checks[i + tmp * i] = False
                tmp += 1
    return primes


def combination(a, b):
    i = 1
    for _i in range(a - b + 1, a + 1):
        i *= _i
    return i // math.factorial(b)


n, m = map(int, input().split())
# start = time.time()
primes = get_primes(m)
elems = []
m_copy = m
divides = dict()
for _p in primes:
    while m_copy % _p == 0:
        m_copy = m_copy // _p
        if str(_p) in divides.keys():
            divides[str(_p)] += 1
        else:
            divides[str(_p)] = 1
if m_copy > 1:
    divides[str(m_copy)] = 1
print(primes)

# print(time.time() - start)
ans = 1
for i in divides.values():
    ans *= combination(i + n - 1, i)
print(ans % (1000000007))
# print(time.time() - start)

Submission status: Wrong Answer

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

import math
class PrimeUtils:
    @staticmethod
    def primes_sieve(n):
        sieve = [True] * (n + 1)
        for i in range(2, n + 1):
            if sieve[i]:
                for j in range(i + i, n + 1, i):
                    sieve[j] = False
        return [i for i, x in enumerate(sieve[2:], 2) if x]
    @staticmethod
    # Prime Factor Decomposition
    def pfd(n):
        rn = math.ceil(math.sqrt(n))
        primes = PrimeUtils.primes_sieve(rn)

        factors = []
        cur = n
        for p in primes:
            cnt = 0
            while True:
                div, rem = divmod(cur, p)
                if rem == 0:
                    cnt += 1
                    cur = div
                else:
                    break
            if cnt != 0:
                factors.append((p, cnt))
        if cur != 1 or n == 1:
            factors.append((cur, 1))
        return factors

import itertools, operator, math
class Combination:
    def __init__(self, fact=math.factorial, div=operator.itruediv):
        self.fact = fact
        self.div = div
    def comb(self, n, m):
        if n < m: return 0
        if m == 0 or n == m: return 1
        return self.div(
                self.fact(n),
                self.fact(n - m) * self.fact(m)
            )

class GFp:
    def __init__(self, p):
        self.p = p
    def inv(self, v):
        return pow(v, self.p - 2, self.p)

class CachedFactorial:
    def __init__(self, n, mod):
        self.mod = mod
        self.fact_cache = list(
                itertools.accumulate(
                        itertools.chain(
                                [1],
                                range(1, n+1)
                        ),
                        lambda a,x: (a * x) % mod
                )
        )
    def factorial(self, n):
        return self.fact_cache[n]

class CachedComb(Combination):
    def __init__(self, n, mod):
        self.mod = mod
        self.gfp = GFp(mod)

        self.n = n
        self.fact = CachedFactorial(n, mod)
        super().__init__(
             self.fact.factorial,
             lambda x, y: (x * self.gfp.inv(y)) % self.mod
        )

ps = PrimeUtils.pfd(M)
cc = CachedComb(N + max(x[1] for x in ps), mod)
ans = 1
for p, c in ps:
    cmb = cc.comb(N - 1 + c, c)
    ans = ans * cmb % mod
print(ans)

Submission status: Wrong Answer

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

import math
class PrimeUtils:
    @staticmethod
    def primes_sieve(n):
        sieve = [True] * (n + 1)
        for i in range(2, n + 1):
            if sieve[i]:
                for j in range(i + i, n + 1, i):
                    sieve[j] = False
        return [i for i, x in enumerate(sieve[2:], 2) if x]
    @staticmethod
    # Prime Factor Decomposition
    def pfd(n):
        rn = math.ceil(math.sqrt(n))
        primes = PrimeUtils.primes_sieve(rn)

        factors = []
        cur = n
        for p in primes:
            cnt = 0
            while True:
                div, rem = divmod(cur, p)
                if rem == 0:
                    cnt += 1
                    cur = div
                else:
                    break
            if cnt != 0:
                factors.append((p, cnt))
        if cur != 1 or n == 1:
            factors.append((cur, 1))
        return factors

ps = PrimeUtils.pfd(M)
print(ps)

import itertools, operator, math
class Combination:
    def __init__(self, fact=math.factorial, div=operator.itruediv):
        self.fact = fact
        self.div = div
    def comb(self, n, m):
        if n < m: return 0
        if m == 0 or n == m: return 1
        return self.div(
                self.fact(n),
                self.fact(n - m) * self.fact(m)
            )

class GFp:
    def __init__(self, p):
        self.p = p
    def inv(self, v):
        return pow(v, self.p - 2, self.p)

class CachedFactorial:
    def __init__(self, n, mod):
        self.mod = mod
        self.fact_cache = list(
                itertools.accumulate(
                        itertools.chain(
                                [1],
                                range(1, n+1)
                        ),
                        lambda a,x: (a * x) % mod
                )
        )
    def factorial(self, n):
        return self.fact_cache[n]

class CachedComb(Combination):
    def __init__(self, n, mod):
        self.mod = mod
        self.gfp = GFp(mod)

        self.n = n
        self.fact = CachedFactorial(n, mod)
        super().__init__(
             self.fact.factorial,
             lambda x, y: (x * self.gfp.inv(y)) % self.mod
        )

cc = CachedComb(N + max(x[1] for x in ps), mod)
ans = 1
for p, c in ps:
    cmb = cc.comb(N - 1 + c, c)
    ans = ans * cmb % mod
print(ans)

Submission status: Wrong Answer

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

def primes_sieve(n):
    sieve = [True] * (n + 1)
    for i in range(2, n + 1):
        if sieve[i]:
            for j in range(i + i, n + 1, i):
                sieve[j] = False
    return [i for i, x in enumerate(sieve[2:], 2) if x]

import math
primes = primes_sieve(math.ceil(math.sqrt(10**9)))

ps = []
t = M
for p in primes:
    u = 0
    while True:
        d, m = divmod(t, p)
        if m == 0:
            u += 1
            t = d
        else:
            break
    if u != 0:
        ps.append((p, u))

import itertools, operator, math
class Combination:
    def __init__(self, fact=math.factorial, div=operator.itruediv):
        self.fact = fact
        self.div = div
    def comb(self, n, m):
        if n < m: return 0
        if m == 0 or n == m: return 1
        return self.div(
                self.fact(n),
                self.fact(n - m) * self.fact(m)
            )

class GFp:
    def __init__(self, p):
        self.p = p
    def inv(self, v):
        return pow(v, self.p - 2, self.p)

class CachedFactorial:
    def __init__(self, n, mod):
        self.mod = mod
        self.fact_cache = list(
                itertools.accumulate(
                        itertools.chain(
                                [1],
                                range(1, n+1)
                        ),
                        lambda a,x: (a * x) % mod
                )
        )
    def factorial(self, n):
        return self.fact_cache[n]

class CachedComb(Combination):
    def __init__(self, n, mod):
        self.mod = mod
        self.gfp = GFp(mod)

        self.n = n
        self.fact = CachedFactorial(n, mod)
        super().__init__(
             self.fact.factorial,
             lambda x, y: (x * self.gfp.inv(y)) % self.mod
        )

cc = CachedComb(N + max([x[1] for x in ps] or [0]), mod)
ans = 1
for p, c in ps:
    cmb = cc.comb(N - 1 + c, c)
    ans = ans * cmb % mod
print(ans)