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


def is_prime(num):
    if (num < 2):
        return False
    elif(num == 2):
        return True
    elif (num % 2 == 0):
        return False
    sqrt_num = int(math.sqrt(num))
    for i in range(3, sqrt_num+1):
        if i % 2 == 0:
            continue
        if (num % i == 0):
            return False
    return True


def combination(n, r):
    if r > n-r:
        r = n-r
    a = 1
    for i in range(n, n-r, -1):
        a = a * i
    d = 1
    for i in range(1, r+1):
        d = d*i
    return a//d


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

m = {}
num = math.ceil(math.sqrt(M))
for i in range(2, num+1):
    if not(is_prime(i)):
        continue
    if M % i == 0:
        m[i] = 0
        _num = M
        while(True):
            if _num % i == 0:
                m[i] += 1
                _num /= i
            else:
                break

ans = 1
mod = 10**9+7
for v in m.values():
    ans *= combination(v+N-1, v)
    ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
import math


def is_prime(num):
    if (num < 2):
        return False
    elif(num == 2):
        return True
    elif (num % 2 == 0):
        return False
    sqrt_num = int(math.sqrt(num))
    for i in range(3, sqrt_num+1):
        if i % 2 == 0:
            continue
        if (num % i == 0):
            return False
    return True


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


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

m = {}
num = math.ceil(math.sqrt(M))
for i in range(2, num+1):
    if not(is_prime(i)):
        continue
    if M % i == 0:
        m[i] = 0
        _num = M
        while(True):
            if _num % i == 0:
                m[i] += 1
                _num /= i
            else:
                break

ans = 1
mod = 10**9+7
for v in m.values():
    ans *= combination(v+N-1, v)
    ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-


'''Snippets for prime.
Available functions:
- is_included: Determine whether it is a prime number.
- generate: Generate a list of prime numbers using sieve of Eratosthenes.
'''


class Prime(object):
    '''Represents a snippet for prime numbers.
    '''

    def __init__(self, number):
        self.number = number
        self._values = []

    def is_included(self) -> bool:
        '''Determine whether it is a prime number.
        Args:
            number: Int of number (greater than 0).
        Returns:
            True if the input number was prime.
            False if the input number was not prime.
        See:
            https://qiita.com/srtk86/items/874639e361917e5016d4
            https://docs.python.org/ja/3/library/2to3.html?highlight=isinstance#2to3fixer-isinstance
        '''

        from math import sqrt

        if (self.number <= 1) or (isinstance(self.number, float)):
            return False

        for i in range(2, int(sqrt(self.number)) + 1):
            if self.number % i == 0:
                return False

        return True

    def generate(self) -> list:
        '''Generate a list of prime numbers using sieve of Eratosthenes.
        Returns:
            A list of prime numbers that is eqaul to or less than the input
            number.
        Landau notation: O(n log log n)
        See:
            https://beta.atcoder.jp/contests/abc110/submissions/3254947
        '''

        if self._values:
            return self._values

        is_met = [True for _ in range(self.number + 1)]
        is_met[0] = False
        is_met[1] = False

        for i in range(2, self.number + 1):
            if is_met[i]:
                self._values.append(i)

                for j in range(2 * i, self.number + 1, i):
                    is_met[j] = False
        return self._values


def count_combinations(n, k, mod):
    ans = 1

    for i in range(1, k + 1):
        ans *= n - i + 1
        ans %= mod
        ans *= pow(i, mod - 2, mod)
        ans %= mod

    return ans


def main():
    from math import sqrt

    n, m = map(int, input().split())
    _prime = Prime(int(sqrt(m)) + 1)
    primes = _prime.generate()
    mod = 10 ** 9 + 7
    ans = 1

    for prime in primes:
        count = 0

        while m % prime == 0:
            count += 1
            m //= prime

        ans *= count_combinations(n + count - 1, count, mod)
        ans %= mod

    if m != 1:
        ans *= count_combinations(n + 1, 1, mod)
        ans %= mod

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-


'''Snippets for prime.
Available functions:
- is_included: Determine whether it is a prime number.
- generate: Generate a list of prime numbers using sieve of Eratosthenes.
'''


class Prime(object):
    '''Represents a snippet for prime numbers.
    '''

    def __init__(self, number):
        self.number = number
        self._values = []

    def is_included(self) -> bool:
        '''Determine whether it is a prime number.
        Args:
            number: Int of number (greater than 0).
        Returns:
            True if the input number was prime.
            False if the input number was not prime.
        See:
            https://qiita.com/srtk86/items/874639e361917e5016d4
            https://docs.python.org/ja/3/library/2to3.html?highlight=isinstance#2to3fixer-isinstance
        '''

        from math import sqrt

        if (self.number <= 1) or (isinstance(self.number, float)):
            return False

        for i in range(2, int(sqrt(self.number)) + 1):
            if self.number % i == 0:
                return False

        return True

    def generate(self) -> list:
        '''Generate a list of prime numbers using sieve of Eratosthenes.
        Returns:
            A list of prime numbers that is eqaul to or less than the input
            number.
        Landau notation: O(n log log n)
        See:
            https://beta.atcoder.jp/contests/abc110/submissions/3254947
        '''

        if self._values:
            return self._values

        is_met = [True for _ in range(self.number + 1)]
        is_met[0] = False
        is_met[1] = False

        for i in range(2, self.number + 1):
            if is_met[i]:
                self._values.append(i)

                for j in range(2 * i, self.number + 1, i):
                    is_met[j] = False
        return self._values


def count_combinations(n, k, mod):
    ans = 1

    for i in range(1, k + 1):
        ans *= n - i + 1
        ans %= mod
        ans *= pow(i, mod - 2, mod)
        ans %= mod

    return ans


def main():
    from math import sqrt

    n, m = map(int, input().split())
    prime = Prime(int(sqrt(m)) + 1)
    primes = prime.generate()
    mod = 10 ** 9 + 7
    ans = 1

    for prime in primes:
        count = 0

        while m % prime == 0:
            count += 1
            m //= prime

        ans *= count_combinations(n + count - 1, count, mod)
        ans %= mod

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

import math 
L=math.floor(math.sqrt(M))

X=dict()

for i in range(2,L+2):
    while M%i==0:
        X[i]=X.get(i,0)+1
        M=M//i

if X==dict():
    X={0:1}


def Combi2(a,b):#aは大きいが、bは小さいとき
    if b>a:
        return 0
    ANS=1
    for i in range(min(b,a-b)):
        ANS=ANS*(a-i)*pow(min(b,a-b)-i,mod-2,mod)

    return ANS%mod

ANS=1
for x in X.values():
    ANS=(ANS*Combi2(x+N-1,x))%mod

print(ANS)

Submission status: Wrong Answer

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

def factorint(x):
  F={}
  i=2
  while i**2<=x:
    if x%i==0:
      c=0
      while x%i==0:
        x=x//i
        c+=1
      F[i]=c
    i+=1
  if x!=1:
    F[x]=1
  return F

def C(n,r):
  a=1
  b=1
  for i in range(r):
    a=a*(n-i)
    b=b*(r-i)
  return((a//b)%(10**9+7))

ans=1
print(factorint(M))
for f in factorint(M):
  k=factorint(M)[f]
  ans*=C(N+k-1,k)        
print(ans%((10**9)+7))

Submission status: Wrong Answer

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

Solution code:
def prime(M):
    lst = []
    i = 2
    while M != 1:
        if M % i == 0:
            lst.append(i)
            M = M // i
        elif i ** 2 > M:
            return [M]
        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: Wrong Answer

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) % (10 ** 9 + 7))

print(val)

Submission status: Wrong Answer

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>=20:
        c=0
        break
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: Wrong Answer

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>=20:
        break
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: Wrong Answer

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

Solution code:
N, M = [int(_) for _ in input().split()]

mod = 10 ** 9 + 7
def comb(x, y):
    if y * 2 > x:
        y = x - y
    result = 1
    for j in range(1, y + 1):
        result *= (x + j - y)
        result //= j
    return result
def homoprod(x, y):
    return comb(x + y - 1, y)

ans = 1
i = 2
for i in range(2, int(M ** 0.5) + 2):
    count = 0
    while M % i == 0:
        count += 1 
        M //= i
    if count > 0:
        ans *= homoprod(N, count)
        ans %= mod
if M > 1:
    ans *= homoprod(N, 1)
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = [int(_) for _ in input().split()]

mod = 10 ** 9 + 7
def comb(x, y):
    if y * 2 > x:
        y = x - y
    ans = 1
    for j in range(1, y + 1):
        ans *= pow(j, mod - 2, mod) * (x - y + j)
        ans %= mod
    return ans
def homoprod(x, y):
    return comb(x + y - 1, y)

ans = 1
i = 2
while i * i <= M:
    count = 0
    while M % i == 0:
        count += 1 
        M //= i
    if count > 0:
        ans *= homoprod(N, count)
        ans %= mod
    i += 1
if M > 1:
    ans *= homoprod(N, 1)
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = [int(_) for _ in input().split()]

mod = 10 ** 9 + 7
def comb(x, y):
    if x // 2 < y:
        return comb(x, x - y)
    ans = 1
    for j in range(1, y + 1):
        ans *= pow(j, mod - 2, mod) * (x - y + j)
        ans %= mod
    return ans
def homoprod(x, y):
    return comb(x + y - 1, y)

ans = 1
for i in range(2, int(M ** 0.5) + 2):
    count = 0
    while M % i == 0:
        count += 1 
        M //= i
    if count > 0:
        ans *= homoprod(N, count)
        ans %= mod
if M > 1:
    ans *= N
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = [int(_) for _ in input().split()]

mod = 10 ** 9 + 7
def comb(x, y):
    if x // 2 < y:
        return comb(x, x - y)
    ans = 1
    for j in range(1, y + 1):
        ans *= pow(j, mod - 2, mod) * (x - y + j)
        ans %= mod
    return ans
def homoprod(x, y):
    return comb(x + y - 1, y)

ans = 1
M_res = M
for i in range(2, int(M ** 0.5) + 2):
    count = 0
    while M_res % i == 0:
        count += 1 
        M_res //= i
    if count > 0:
        ans *= homoprod(N, count)
        ans %= mod
if M_res == M:
    ans = N
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = [int(_) for _ in input().split()]

mod = 10 ** 9 + 7
def comb(x, y):
    if x // 2 < y:
        return comb(x, x - y)
    ans = 1
    for j in range(1, y + 1):
        ans *= pow(j, mod - 2, mod) * (x - y + j)
        ans %= mod
    return ans
def homoprod(x, y):
    return comb(x + y - 1, y)

ans = 1
for i in range(2, int(M ** 0.5) + 2):
    count = 0
    while M % i == 0:
        count += 1 
        M //= i
    if count > 0:
        ans *= homoprod(N, count)
        ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
import math

def InvMod(i, pow, mod): #階乗のmodを計算
    if pow == 1:
        return i % mod
    else:
        if pow % 2 == 0:
            return InvMod((i**2) % mod, pow//2, mod) % mod
        else:
            return InvMod((i**2) % mod, pow//2, mod) * i % mod

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

N, M = map(int, input().split())
max = int(math.sqrt(M))
mod = 7 + 10**9
Nfact = 1
for i in range(1, N):
    Nfact *= i
    Nfact %= mod
NfactInv = InvMod(Nfact, mod-2, mod)
NaFact = [Nfact] 
for a in range(1, 31):
    new = NaFact[-1] * (N+a-1) // a
    NaFact.append(new % mod)

P = []
for i in range(2, max+1):
    if Prime(i):
        if M % i == 0:
            P.append(i)
            if Prime(M//i) and i**2 != M:
                P.append(M//i)

ans = 1
for p in P:
    C, pow = M, 0
    while C % p == 0:
        pow += 1
        C //= p
    ans *= NaFact[pow] * NfactInv % mod
    ans %= mod

print(ans)

Submission status: Wrong Answer

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
_M=M
while(i <=M and i**2 <=_M):
    if(M%i==0):
        if(i in soinsuubunkai):
            soinsuubunkai[i]+=1
        else:
            soinsuubunkai[i]=1
        M//=i
    else:
        i+=1

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

Submission status: Wrong Answer

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
M
while(i*2 <=M):
    if(M%i==0):
        if(i in soinsuubunkai):
            soinsuubunkai[i]+=1
        else:
            soinsuubunkai[i]=1
        M//=i
    else:
        i+=1

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

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
rec = []
MOD = 10 ** 9 + 7
K = M
for i in range(2, int(M ** 0.5) + 1):
    if K % i == 0:
        tmp = 0
        while K % i == 0:
            tmp += 1
            K //= i

        rec.append((i, tmp))

Q = 10 ** 6 + 1
fact = [0] * Q
rfact = [0] * Q
fact[0] = 1
for i in range(1, Q):
    fact[i] = fact[i - 1] * i % MOD

rfact[Q - 1] = pow(fact[Q - 1], MOD - 2, MOD)
for i in range(Q - 2, -1, -1):
    rfact[i] = rfact[i + 1] * (i + 1) % MOD


def comb(n, r):
    return fact[n] * rfact[n - r] * rfact[r] % MOD


num = 1
for i in range(len(rec)):
    num *= comb(N + rec[i][1] - 1, rec[i][1])
    num %= MOD

print(num)

Submission status: Wrong Answer

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

divs = []
while m != 0:
    flag = 0
    for i in range(2, int(m**0.5)+1):
        if m % i == 0:
            flag = 1
            divs.append(i)
            break
    if flag == 1:
        m = m / i
    else:
        divs.append(m)
        break
divs.sort()
divs_num = []
num = 0
first = divs[0]
divs.append(0)
for i in range(len(divs)):
    if divs[i] == first:
        num += 1
    else:
        divs_num.append(num)
        num = 1
        first = divs[i]


def algorithm(k):
    result = 1
    division = 1
    num = n + k - 1
    num2 = 1
    for i in range(min(k, n-1)):
        result *= num
        num -= 1
        division *= num2
        num2 += 1
    return result / division

divs_num = map(algorithm, divs_num)


result = 1
for i in divs_num:
    result *= i
print result % (10**9+7)

Submission status: Wrong Answer

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

divs = []
while m != 0:
    flag = 0
    for i in range(2, int(m**0.5)+1):
        if m % i == 0:
            flag = 1
            divs.append(i)
            break
    if flag == 1:
        m = m / i
    else:
        divs.append(m)
        break
divs.sort()
divs_num = []
num = 0
first = divs[0]
divs.append(0)
for i in range(len(divs)):
    if divs[i] == first:
        num += 1
    else:
        divs_num.append(num)
        num = 1
        first = divs[i]


def algorithm(k):
    result = 1
    division = 1
    num = n + k - 1
    num2 = 1
    for i in range(min(k, n-1)):
        result *= num
        num -= 1
        division *= num2
        num2 += 1
    return result / division

divs_num = map(algorithm, divs_num)


result = 1
for i in divs_num:
    result *= i
print result

Submission status: Wrong Answer

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

divs = []

while m != 0:
    flag = 0
    for i in range(2, int(m**0.5)+1):
        if m % i == 0:
            flag = 1
            divs.append(i)
            break
    if flag == 1:
        m = m / i
    else:
        divs.append(m)
        break
        
divs.sort()
divs_num = []
num = 0
first = divs[0]
divs.append(0)
for i in range(len(divs)):
    if divs[i] == first:
        num += 1
    else:
        divs_num.append(num)
        num = 1
        first = divs[i]


def algorithm(k):
    result = 1
    num = n + k - 1
    for i in range(n-1):
        result *= num
        num -= 1
    return result

print sum(map(algorithm, divs_num))

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

        i += 1

    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()