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

Solution (Python):



import array
import collections
import functools
import itertools
import math
import random


M = 10 ** 9 + 7


def sieve_of_eratosthenes(end, typecode="L"):
    """Enumerates the prime numbers below the given integer.
    :param int end: Prime numbers below this integer will be enumerated.
    :param str typecode: The type of the array to be returned (optional).
    :return: The array of the prime numbers.
    :rtype: :class:`array.array`
    """

    assert end > 1
    is_prime = array.array("B", (True for i in range(end)))
    is_prime[0] = False
    is_prime[1] = False
    primes = array.array(typecode)
    for i in range(2, end):
        if is_prime[i]:
            primes.append(i)
            for j in range(2 * i, end, i):
                is_prime[j] = False
    return primes


def factorize_trial_division(n, typecode="L"):
    """Factorizes the given integer in prime numbers by trial division.
    :param int n: The integer to be factorized.
    :param str typecode: The type of the array to be returned (optional).
    :return: The array of factors.
    :rtype: :class:`array.array`
    """
    factors = array.array(typecode)
    if n < 2:
        return factors
    for p in sieve_of_eratosthenes(math.ceil(math.sqrt(n)) + 1):
        if p * p > n:
            break
        while n % p == 0:
            factors.append(p)
            n //= p
    if n > 1:
        factors.append(n)
    return factors


def is_prime_miller_rabin(n, k=50):
    """Determing whether the given integer is prime by the Miller-Rabin test.
    :param int n: The integer to be checked.
    :param int k: The parameter representing the accuracy of the determination.
    :return: Whether n is prime or not.
    :rtype: bool
    """
    assert n > 0
    if n == 2:
        return True
    elif n == 1 or n % 2 == 0:
        return False
    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1
    for _ in range(k):
        a = random.randint(1, n - 1)
        if pow(a, d, n) != 1:
            for r in range(0, s):
                if pow(a, d * 2 ** r, n) == n - 1:
                    break
            else:
                return False
    return True


class ModPrime(object):

    def __init__(self, max_n=500000, mod=M):
        
        self.max_n = max_n
        assert is_prime_miller_rabin(mod)
        self.mod = mod
        self.invs = [None, 1]
        for i in range(2, self.max_n + 1):
            self.invs.append(mod - mod // i * self.invs[mod % i] % mod)
        self.facts = [1]
        self.fact_invs = [1]
        for i in range(1, self.max_n + 1):
            self.facts.append(self.facts[i - 1] * i % mod)
            self.fact_invs.append(self.fact_invs[i - 1] * self.invs[i] % mod)
    
    def inv(self, n):
        return self.invs[n]
    
    def fact(self, n):
        return self.facts[n]
    
    def fact_inv(self, n):
        return self.fact_invs[n]
    
    def comb(self, n, r):
        if r < 0 or r > n:
            return 0
        return self.fact(n) * self.fact_inv(r) % self.mod * self.fact_inv(n - r) % self.mod
    
    def multi_choose(self, n, r):
        return self.comb(n + r - 1, r)


def mod_prod(ys, mod=M):
    xs = itertools.chain((1, ), ys)
    return functools.reduce(lambda x, y: x * y % mod, xs) % mod


def solve(n, m, mod=M):
    fs = collections.Counter(factorize_trial_division(m))
    mp = ModPrime(mod=M)
    res = mod_prod((mp.multi_choose(n, v) for v in fs.values()), mod=M)
    return res


def main():
    n, m = (int(z) for z in input().split())
    res = solve(n, m)
    print(res)

if __name__ == '__main__':
    main()

Solution (Python):
N, M = map(int, input().split())
ex = []
i = 2
while i**2 <= M:
    j = 0
    while M % i == 0:
        M //= i
        j += 1
    if j != 0:
        ex.append(j)
    i += 1
if M > 1: 
    ex.append(1)

mod = 10**9+7
ans = 1
for e in ex: 
    temp = 1
    for i in range(e):
        temp *= (e+N-1 - i)
    for i in range(e):
        temp //= (e - i)
    ans *= temp
    ans %= mod
print(ans)

Solution (Python):
M = 10 ** 9 + 7

def main():
    n, m = [int(s) for s in input().split()]

    print(solve(m, n, 10 ** 9 + 7))

def solve(m, n, mod):
    r = 1

    for _, c in get_prime_factors(m):
        r = r * mod_comb(c + n - 1, c, mod) % mod
    return r

def mod_comb(n, k, m):
    r = 1
    for i in range(1, k + 1):
        r = r * (n - k + i) * mod_inv(i, m) % m
    return r

def mod_inv(n, m):
    r0, r1 = n, m
    x, y, u, v = 1, 0, 0, 1

    while r1:
        k, r0, r1 = r0 // r1, r1, r0 % r1
        x, y, u, v = u, v, x - k * u, y - k * v

    if r0 != 1:
        raise ValueError

    return x

def get_prime_factors(n):
    from itertools import count, takewhile
    r = n

    for i in takewhile(lambda x: x * x <= r, count(2)):
        c = 0
        while r % i == 0:
            c += 1
            r //= i
        yield i, c

    if r != 1:
        yield r, 1

main()

Solution (Python):
n,m=map(int,input().split())
i=2
s=[]
while i*i<=m:
  j=0
  while m % i == 0:
    m//=i
    j+=1 
  if j:
    s+=[j]
  i+=1
a=1
if m > 1:
  s+=[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)

Solution (Python):
import sys

MOD = 10 ** 9 + 7

def main():
    n, m = [int(s) for s in input().split()]
    print(solve(m, n))

def solve(m, n):
    factors = list(get_prime_factors(m))
    h = max((c for f, c in factors), default=0)

    table = dict()
    table[1] = [1 for _ in range(h + 1)]

    i = 1
    while i < n:
        j = n & (i - 1)
        table[i * 2] = [0 for _ in range(h + 1)]
        if n & i != 0 and j != 0:
            table[i + j] = [0 for _ in range(h + 1)]
        for x in range(h + 1):
            for y in range(h + 1 - x):
                table[i * 2][x + y] = (table[i * 2][x + y] + table[i][x] * table[i][y]) % MOD
                if n & i != 0 and j != 0:
                    table[i + j][x + y] = (table[i + j][x + y] + table[i][x] * table[j][y]) % MOD

        if n & i == 0:
            del table[i]
        if n & i != 0 and j != 0:
            del table[i]
            del table[j]

        i *= 2

    ans = 1
    for f, c in factors:
        ans = ans * table[n][c] % MOD
    return ans

def get_prime_factors(n):
    import itertools

    m = n
    for i in itertools.count(2):
        if i * i > m:
            break

        c = 0
        while True:
            x, y = divmod(m, i)
            if y != 0:
                break
            c += 1
            m = x
        if c != 0:
            yield i, c

    if m != 1:
        yield m, 1


main()

Solution (Python):
from math import factorial
MOD = 10**9 + 7

def prime_factor(n):
    res = []
    d = 2
    while d * d <= n:
        if n % d == 0:
            cnt = 0
            while n % d == 0:
                cnt += 1
                n //= d
            res.append(cnt)
        d += 1
    if n > 1:
        res.append(1)
    return res

N, M = map(int, input().split())
ans = 1
for c in prime_factor(M):
    for i in range(c):
        ans *= N + i
    ans //= factorial(c)
    ans %= MOD
print(ans)

Solution (Python):
MOD = 10 ** 9 + 7

def mod_pow(a, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return mod_pow(a, p // 2) ** 2 % MOD
    else:
        return a * mod_pow(a, p - 1) % MOD

def calc_comb(a, b):
    if b > a - b:
        return calc_comb(a, a - b)
    ans_mul, ans_div = 1, 1
    for i in range(b):
        ans_mul *= a - i
        ans_div *= i + 1
        ans_mul %= MOD
        ans_div %= MOD
    return ans_mul * mod_pow(ans_div, MOD - 2) % MOD

def main():
    N, M = map(int, input().split())
    i = 2
    ans = 1
    while i * i <= M:
        if M % i == 0:
            cnt = 0
            while M % i == 0:
                cnt += 1
                M //= i
            ans *= calc_comb(N + cnt - 1, N - 1)
            ans %= MOD
        i += 1
    if M > 1:
        ans *= calc_comb(N + 1 - 1, N - 1)
        ans %= MOD
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import math
n,m = map(int,input().split())
mm = int(math.sqrt(m))
s = {}
for i in range(2,mm+2):
    if m%i != 0:
        continue
    while m%i == 0:
        m = m//i
        s[i] = s.get(i, 0) + 1
    if m == 1:
        break
if m>=2:
    s[1] = 1
ans = 1
mod = 10**9+7
for i in s.values():
    for j in range(1,i+1):
        ans = ans * (n+j-1)//(j)
    ans %=mod
print(ans)

Solution (Python):
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import Counter

def factorize(n: int):
    d = Counter()
    m= 2
    
    while m*m <= n:
        while n%m == 0:
            n //= m
            d[m] += 1
            
        m += 1
        
    if n > 1:
        d[n] += 1
        
    return d


def inv_mod(n:int, mod:int) -> list:
    inv = [0,1]
    for i in range(2,n+1):
        inv.append(mod - ((mod//i)*inv[mod%i]) % mod)
    return inv
       

def fact(n:int, mod:int) -> list:
    fac = [1,1]
    res = 1
    for i in range(2,n+1):
        res = res*i%mod
        fac.append(res)
    return fac


def fact_inv(n:int, inv:list, mod:int) -> list:
    facInv = [1,1]
    for i in range(2,n+1):
        facInv.append(facInv[i-1]*inv[i] % mod)
    return facInv
        

def nCr(n:int, r:int, mod:int, fac:list, facInv:list) -> int:
    if not (0<=r and r<=n):
        return 0
    
    return ((fac[n]*facInv[r]) % mod) * facInv[n-r] % mod


def nHr(n:int, r:int, mod:int, fac:list, facInv:list) -> int:
    if r<0 or n<0:
        return 0
    
    else:
        return nCr(n+r-1,r,mod,fac,facInv)
    
MOD = 10**9+7

n,m = li()


inv = inv_mod(n+100,MOD)
fac = fact(n+100,MOD)
fac_inv = fact_inv(n+100,inv,MOD)

primes = factorize(m)
ans = 1
for p in primes.values():
    ans = ans * nHr(n,p,MOD,fac,fac_inv) % MOD
    
print(ans)

Solution (Python):
from sys import stdin


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


def comb(n, r):
    a = 1
    for num in range(n, n - r, -1):
        a *= num

    b = 1
    for num in range(r, 0, -1):
        b *= num

    return a // b


N, M = [int(i) for i in stdin.readline().rstrip().split()]

lst = num_of_prime_factorization(M)
ans = 1

for b in lst:
    ans *= comb(b + N - 1, b)

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

Solution (Python):

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

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

aP = fPrimeCounter(iM)



iRet = 1
for i in aP:
    
    iRet *= fnCr(i+iN-1,i,iD)
iRet %= iD
print(iRet)

Solution (Python):
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): 
    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)

Solution (Python):
from collections import Counter

from scipy.misc import comb

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

mod = 10**9 + 7


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


p = prime_decomposition(M)
p = Counter(p)

ans = 1
for pi in p.values():
    res = comb(pi + N - 1, N - 1, exact=True)
    ans = (ans * res) % mod
print(ans)

Solution (Python):
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)

Solution (Python):

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

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


def fBiPow(iX,iN,iD):
    iY = 1
    while iN > 0:
        if iN % 2 == 0:
            iX = iX * iX % iD
            iN = iN // 2
        else:
            iY = iX * iY % iD
            iN = iN - 1
    return iY

aP = fPrimeCounter(iM)
if len(aP) == 0:
    print(1)
    exit()
iMax = max(aP) + iN - 1
aM = [1] * (iMax + 1)

for i in range(1,iMax + 1):
    aM[i] = aM[i-1] * i  % iD
aInvM = [1]* (iMax + 1)
aInvM[iMax] = fBiPow(aM[iMax],iD-2,iD)

for i in range(iMax,0,-1):
    aInvM[i-1] = aInvM[i]*i % iD

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

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

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

    return aRet


def fBiPow(iX,iN,iD):
    iY = 1
    while iN > 0:
        if iN % 2 == 0:
            iX = iX * iX % iD
            iN = iN // 2
        else:
            iY = iX * iY % iD
            iN = iN - 1
    return iY

aP = fPrimeCounter(iM)
if aP == [] :
    print (1)
else:
    iMax = max(aP) + iN - 1
    aM = [1] * (iMax + 1)
    
    for i in range(1,iMax + 1):
        aM[i] = aM[i-1] * i  % iD
    aInvM = [1]* (iMax + 1)
    aInvM[iMax] = fBiPow(aM[iMax],iD-2,iD)
    
    for i in range(iMax,0,-1):
        aInvM[i-1] = aInvM[i]*i % iD

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

Solution (Python):
import copy

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


import math
x=math.floor(math.sqrt(10**9))
L=math.floor(math.sqrt(x))
Primelist=[i for i in range(x+1)]
Primelist[1]=0
for i in Primelist:
    if i>L:
        break
    if i==0:
        continue
    for j in range(2*i,x+1,i):
        Primelist[j]=0
Primes=[Primelist[j] for j in range(x+1) if Primelist[j]!=0]

def fact(M):
    if M==1:
        return {1}
    
    DICT=dict()
    i=0
    while M!=1 and i<len(Primes):
        if M%Primes[i]==0:
            DICT[Primes[i]]=DICT.get(Primes[i],0)+1
            M=M//Primes[i]
        else:
            i+=1

    if M!=1:
        DICT[M]=1

    VALUES=list(DICT.values())
    KEYS=list(DICT.keys())

    LIST=[1]

    for i in range(len(DICT)):
        NOWLIST=copy.copy(LIST)
        for l in NOWLIST:
            for j in range(0,VALUES[i]+1):
                LIST.append(l*KEYS[i]**j)

    return set(LIST)

def Combi2(a,b):
    if b>a:
        return 0
    ANS=1
    for i in range(min(b,a-b)):
        ANS=ANS*(a-i)%mod*pow(min(b,a-b)-i,mod-2,mod)%mod

    return ANS%mod



SET=fact(M)
factor=dict()

for j in SET:
    factor[j]=fact(j)

DP=dict()
defaultans=[0 for i in range(40)]
defaultans[1]=1
defaultans=tuple(defaultans)

def dp(m):
    ANS=[0 for i in range(40)]
    if m==1:
        return defaultans
    
    for j in factor[m]:
        

        if j==1:
            continue
        else:
            if DP.get(m//j,-1)!=-1:
                NEXT=DP[m//j]
            else:
                NEXT=dp(m//j)

            for k in range(39):
                ANS[k+1]=(ANS[k+1]+NEXT[k])%mod

            

        DP[m]=ANS
    return ANS
            
LIST=dp(M)
ANS=0
for i in range(40):
    if LIST[i]!=0:
        ANS=ANS+Combi2(N,i-1)*LIST[i]%mod

print(ANS%mod)

Solution (Python):
import math


def modinv(a, b, m):
    
    
    
    for i in range(m):
        if (i * m + 1) % b == 0:
            tmp = int((i * m + 1) / b)
            break

    
    return (tmp * a) % m


def factoring(n):
    pf = {}
    num = n

    if n == 1:
        return {}

    while True:
        flag = 0

        for i in range(2, math.floor(math.sqrt(n)) + 1):
            if num % i == 0:
                num = num / i
                flag = 1
                if i in pf:
                    pf[i] += 1
                else:
                    pf[i] = 1

                if num == 1.0:
                    return pf
                else:
                    break

        if flag == 0:
            if num in pf:
                pf[num] += 1
            else:
                pf[num] = 1
            return pf


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




MOD = 10 ** 9 + 7


pf = factoring(M)

ans = 1
for key in pf:
    for i in range(pf[key]):
        ans = ans * (N - 1 + pf[key] - i) % MOD
    for i in range(2, pf[key] + 1):
        ans = modinv(ans, i, MOD)

print(ans)

Solution (Python):
from math import log2
N, M = map(int, input().split())

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 


for i in range( 2, N + 1 + 30 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

Divs = {}

i = 2
while i * i <= M:
  first_time = True
  while M % i == 0:
    if first_time:
      Divs[i] = 1
      first_time = False
    else:
      Divs[i] = Divs[i] + 1
    M = M // i
  i += 1

if M > 1:
  Divs[M] = 1

ans = 1
for k,v in Divs.items():
  ans = ans * cmb(v+N-1,v,mod) % mod


print(ans)

Solution (Python):
def framod(n,mod):
    a=1
    for i in range(1,n+1):
        a=a * i % mod
    return a

def power(n,r,mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod
    
def comb(n,k,mod):
    if n<0 or k<0 or n<k: return 0
    if n==0 or k==0: return 1
    a=framod(n,mod)
    b=framod(k,mod)
    c=framod(n-k,mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod

n,m=map(int, input().split())
pf={}
for i in range(2,int(m**0.5)+1):
    while m%i==0:
        pf[i]=pf.get(i,0)+1
        m//=i
if m>1:pf[m]=1

mod=10**9+7   
ans=1
for i in pf:
    ans=(ans * comb(pf[i]+n-1,pf[i],mod)) % mod
print(ans)

Solution (Python):
from collections import Counter
def primes(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n = n // i
      table.append(i)
    i += 1
  if n > 1:
    table.append(n)
  return table

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

N,M = map(int, input().split())
ans = 1
for v in Counter(primes(M)).values():
  ans *= comb(N+v-1,N-1)
  ans %= 10**9+7
print(ans)

Solution (Python):
n,m=map(int,input().split())
pw = []
d = 2
while d*d <= m:
  e = 0
  while m % d == 0:
    e += 1
    m //= d
  if e > 0: pw.append(e)
  d += 1
if m > 1: pw.append(1)
ans = 1
for e in pw:
  comb = 1
  for i in range(e):
    comb = comb * (n+i) // (1+i)
  ans = ans * comb % 1000000007
print(ans)