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: Accepted

Solution code:
import numpy as np
N,M=list(map(int,input().split()))
n=4*10**4
prime=[i for i in range(n)]
prime[1]=0
for i in range(2,n):
    tmp =i*i
    if prime[tmp]==0 or tmp > n:
        break
    while tmp<n:
        prime[tmp]=0
        tmp+=i

prime=np.array(prime)
prime=prime[prime!=0]

dic={}
for x in prime:
    while M%x==0:
        if dic.get(x,0)==0:
            dic[x]=1
        else:
            dic[x]+=1
        M/=x
    if M==1:
        break
if M !=1:
    dic[M]=1
ans = 1
for x in dic.values():
    tmp1=1
    tmp2=1
    for i in range(x,0,-1):
        tmp1*=(i+N-1)
        tmp2*=i
    ans*=tmp1//tmp2
    ans%=10**9+7
print(int(ans))

Submission status: Accepted

Solution code:
import math

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

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

dic = {}
p = 2
while True:
    if m==1:
        break
    if p > math.floor(math.sqrt(m))+1:
        if dic.get(m) is None:
            dic[m] = 1
        else:
            dic[m] += 1
        break
    if m % p == 0:
        if dic.get(p) is None:
            dic[p] = 1
        else:
            dic[p] += 1
        m = m//p
        p=1
    p+=1

def pow(n,e):
    ret=1
    b=n
    while e > 0:
        if e % 2 == 1:
            ret = ret * b % mod
        b = b * b % mod
        e = e//2
    return ret
    
def inv(n):
    return pow(n,mod-2)

def nck(n,k):
    ret = 1
    for i in range(1,k+1):
        ret *= (n-i+1) % mod
        ret %= mod
        ret *= inv(i) % mod
        ret %= mod
    return ret
    
ret=1
for x in dic.keys():
    ret = (ret * nck(n+dic[x]-1,min(n-1,dic[x]))) % mod

print(ret)

Submission status: Accepted

Solution code:
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

# nの逆元のリスト
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
       
# nの階乗のリスト
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

# nの階乗の逆元のリスト
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 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


n,m = li()

MOD = 10**9+7

# 二項係数の準備
inv = inv_mod(n+100,MOD)
fac = fact(n+100,MOD)
facInv = fact_inv(n+100,inv,MOD)


primes = factorize(m)
ans = 1

if n == 1 or m == 1:
    print(ans)
else:
    for pi in primes.values():
        ans = ans * nCr(n+pi-1, pi, MOD, fac, facInv) % MOD
    print(ans)

Submission status: Accepted

Solution code:
def d_factorization(N, M):
    def prime_factorization_dict(n):
        if n == 1:
            return {2: 0}  # 1は素数の0乗の積とみなす
        i = 2
        table = {}
        while i**2 <= n:
            table[i] = 0
            while n % i == 0:
                table[i] += 1
                n //= i
            if table[i] == 0:
                table.pop(i)
            i += 1
        if n > 1:
            table[n] = 1
        return table

    class Combination(object):
        def __init__(self, n, mod):
            self.mod = mod
            # フェルマーの小定理による組合せの計算
            self.factorial = [1] * (n + 1)  # 0!からn!の結果を格納
            for k in range(1, n):
                self.factorial[k + 1] = (self.factorial[k] * (k + 1)) % mod
            # k!のmodにおける逆元を計算
            self.fact_inv = [1] * (n + 1)
            self.fact_inv[n] = pow(self.factorial[n], mod - 2, mod)
            for k in reversed(range(1, n + 1)):
                self.fact_inv[k - 1] = (self.fact_inv[k] * k) % mod

        def comb(self, n, r):
            if n < 0 or r < 0 or n < r:
                return 0
            return (self.factorial[n] * self.fact_inv[r] * self.fact_inv[n - r]) % self.mod

        def comb_with_repetition(self, n, r):
            if n == 0 and r > 0:
                return 0
            if n >= 0 and r == 0:
                return 1
            return self.comb(n + r - 1, r)

    MOD = 10**9 + 7
    prime_m = prime_factorization_dict(M)
    c = Combination(max(prime_m.values()) + N - 1, MOD)
    ans = 1
    for b in prime_m.values():
        ans = (ans * c.comb_with_repetition(N, b)) % MOD

    return ans

N, M = [int(i) for i in input().split()]
print(d_factorization(N, M))

Submission status: Accepted

Solution code:
from collections import Counter
n, m = map(int, input().split())
cl = []
for i in range(2, int(m ** .5) + 1):
    while m % i == 0:
        cl.append(i)
        m //= i
if m > 1:
    cl.append(m)

def comb(x, y):
    y = min(y, x - y)
    a = 1
    for i in range(x, x - y, -1):
        a *= i
    b = 1
    for i in range(1, y + 1):
        b *= i
    return a // b

ans = 1
mod = 10 ** 9 + 7
for t in Counter(cl).values():
    ans = ans * comb(t + n - 1, t) % mod
print(ans)

Submission status: Accepted

Solution code:
import math
(n, m)  =map(int, input().split())
factor = []
for i in range(2 , int(math.sqrt(m)) + 1):
    count = 0
    while m % i == 0:
        m = m / i
        count += 1
    if count != 0:
        factor.append(count)
if m > 1:
    factor.append(1)
sum = 1
for i in range(len(factor)):
    tmpn = n + factor[i] - 1
    d = 1
    for j in range(factor[i]):
        sum = sum * (tmpn - j)
        d = d * (factor[i] - j)
    sum = sum // d % 1000000007
print(sum)

Submission status: Accepted

Solution code:
import math
(n, m)  =map(int, input().split())
sqm = math.sqrt(m)
map = {}
i = 2
y = m
while m != 1 and sqm >= i:
    if m % i == 0 :
        m = m / i
        if i in map:
            map[i] += 1
        else:
            map[i] = 1
    else:
        i += 1
if m > 1:
    map[m] = 1

sum = 1
for i in map:
    tmpn = n + map[i] - 1
    c = 1
    d = 1
    e = 1
    for j in range(map[i]):
        c = c * (tmpn - j)
        d = d * (map[i] - j)
    e = e * c // d
    
    sum = sum * e % 1000000007
print(sum )

Submission status: Accepted

Solution code:
from math import sqrt

def cal_factors(num):
    factors = {}
    maxmod = int(sqrt(num)) + 1
    for mod in range(2, maxmod):
        i = 0
        while True:
            d, q = divmod(num, mod)
            if q == 0:
                num = d
                i += 1
                factors[mod] = i
            else:
                break

    if num > 1:
        factors[num] = 1

    return factors


def comb(n, r, mod):
    result = 1
    r = min(r, n-r)
    for i in range(n, n-r, -1):
        result *= i
    for i in range(2, r+1):
        result //= i

    return result % mod


n, m = [int(v) for v in input().split()]

mod = 1000000000 + 7
factors = cal_factors(m)
ans = 1
for v in factors.values():
    ans *= comb(v + n - 1, v, mod)
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
from math import sqrt
from scipy.misc import comb

def cal_factors(num):
    factors = {}
    maxmod = int(sqrt(num)) + 1
    for mod in range(2, maxmod):
        i = 0
        while True:
            d, q = divmod(num, mod)
            if q == 0:
                num = d
                i += 1
                factors[mod] = i
            else:
                break

    if num > 1:
        factors[num] = 1

    return factors


n, m = [int(v) for v in input().split()]

mod = 1000000000 + 7
factors = cal_factors(m)
ans = 1
for v in factors.values():
    ans *= comb(v + n - 1, v, exact=True) % mod
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import unittest
import math

MOD = 10**9+7


def func(n,m):
    fac = [1 for _ in range(n+100)]
    finv = [1 for _ in range(n+100)]
    inv = [1 for _ in range(n+100)]
    for i in range(2,n+100):
        fac[i] = (fac[i-1]*i)%MOD
        inv[i] = (MOD - inv[MOD%i] * (MOD//i))%MOD
        finv[i] = (finv[i-1]*inv[i])%MOD

    def comb(a,b):
        return (fac[a]*((finv[b]*finv[a-b])%MOD))%MOD

    fact = {}
    for x in range(2, math.ceil(math.sqrt(m))+1):
        while m%x==0:
            if x not in fact:
                fact[x] = 0
            fact[x] += 1
            m = m//x
        if m==1:
            break
    if m!=1:
        fact[m] = 1

    ret = 1
    for k in fact.values():
        ret *= comb(k+n-1,k)
        ret %= MOD
    return ret

class Test(unittest.TestCase):
    def test(self):
        self.assertEqual(func(2,6), 4)
        self.assertEqual(func(3,12), 18)
        self.assertEqual(func(100000, 1000000000), 957870001)
        self.assertEqual(func(2,3), 2)

if __name__ == '__main__':
    n,m = map(int, input().split())
    print(func(n,m))
    # unittest.main()

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7


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


def comb(a, b):
    b = min(b, a - b)
    if b < 0:
        return 0
    elif b == 0:
        return 1
    elif b == 1:
        return a
    else:
        return (((a % MOD) * pow(b, MOD - 2, MOD) % MOD) * comb(a - 1, b - 1)) % MOD


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

ans = 1
for power in prime_factorization(M):
    ans *= comb(N - 1 + power, power)
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7


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


def comb(a, b):
    b = min(b, a - b)
    if b < 0:
        return 0
    elif b == 0:
        return 1
    elif b == 1:
        return a
    else:
        return (a % MOD) * pow(b, MOD - 2, MOD) % MOD * comb(a - 1, b - 1) % MOD


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

ans = 1
for power in prime_factorization(M):
    ans *= comb(N - 1 + power, power)
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
from math import sqrt

def cal_factors(num):
    factors = {}
    maxmod = int(sqrt(num)) + 1
    for mod in range(2, maxmod):
        i = 0
        while True:
            d, q = divmod(num, mod)
            if q == 0:
                num = d
                i += 1
                factors[mod] = i
            else:
                break

    if num > 1:
        factors[num] = 1

    return factors


def comb(n, r, mod):
    result = 1
    r = min(r, n-r)
    for i in range(n, n-r, -1):
        result *= i
    for i in range(2, r+1):
        result //= i
    result %= mod

    return result


n, m = [int(v) for v in input().split()]

mod = 1000000000 + 7
factors = cal_factors(m)
ans = 1
for v in factors.values():
    ans *= comb(v + n - 1, v, mod)
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
from math import sqrt

def cal_factors(num):
    factors = {}
    i = 0
    while True:
        d, q = divmod(num, 2)
        if q == 0:
            num = d
            i += 1
            factors[2] = i
        else:
            break

    maxmod = int(sqrt(num)) + 1
    for mod in range(3, maxmod, 2):
        i = 0
        while True:
            d, q = divmod(num, mod)
            if q == 0:
                num = d
                i += 1
                factors[mod] = i
            else:
                break

    if num > 1:
        factors[num] = 1

    return factors


def comb(n, r, mod):
    result = 1
    r = min(r, n-r)
    for i in range(n, n-r, -1):
        result *= i
    for i in range(2, r+1):
        result //= i
    result %= mod

    return result


n, m = [int(v) for v in input().split()]

mod = 1000000000 + 7
factors = cal_factors(m)
ans = 1
for v in factors.values():
    ans *= comb(v + n - 1, v, mod)
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
import math
import sys
import collections


mod = 1000000007
sys.setrecursionlimit(mod)
fact = {1: 1}


def run(n, m):
    # print('{}を{}個の数列で表現'.format(m, n))
    ans = 1
    primes = []
    for i in range(2, m):
        if m == 1:
            break
        if i*i > m:
            break
        if m % i == 0:
            cnt = 0
            while m % i == 0:
                cnt += 1
                m //= i
                primes.append(i)
            ans *= comb(cnt+n-1, n-1)
            ans %= mod
    # counts = collections.Counter(primes)
    # print(counts)
    # for (_, v) in counts.items():
    #     ans *= comb(v+n-1, n-1)
    #     ans %= mod
    if m != 1:
        ans *= n
        ans %= mod
    return ans


def comb(n, r):
    if r > (n-r):
        r = n-r
    mul = 1
    div = 1
    for i in range(r):
        mul *= n-i
        div *= i+1
        mul %= mod
        div %= mod
    # mul = math.factorial(n) // math.factorial(n - r)
    # div = math.factorial(r)
    # mul = factorial(n) // factorial(n - r)
    # div = factorial(r)
    mul %= mod
    div %= mod
    return (mul * modpow(div, (mod-2))) % mod


'''
def factorial(n):
    if n in fact:
        return fact[n]
    else:
        fact[n] = n*factorial(n-1)
        return fact[n]
'''


def modpow(a, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        halfp = p // 2
        half = modpow(a, halfp)
        return int((half * half) % mod)
    else:
        return int((a * modpow(a, p-1)) % mod)


def main():
    n, m = map(int, input().split())
    print(run(n, m))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Sep 23 22:00:37 2018
ABC110D
@author: maezawa
"""
import collections

def comb(n, r):
    if n == 0 or r == 0:
        return 1
    return comb(n, r-1)*(n-r+1)//r

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

mod = 10**9+7
np = int(10**4.5 + 10)
is_prime = [True]*(np+1)

is_prime[0] = False
is_prime[1] = False

for i in range(2, np//2):
    if is_prime[i] == True:
        for j in range(2*i,np+1,i):
            is_prime[j] = False

prime_numbers = [i for i in range(np+1) if is_prime[i]]

pds = []
for i in prime_numbers:
    if i > m//2:
        break
    md = m
    while md%i == 0:
        pds.append(i)
        md = md//i
mul = 1
for i in pds:
    mul *= i
if m != mul:
    pds.append(m//mul)

#print(pds)
cpds = collections.Counter(pds)
#print(cpds)
ans = 1
for i in cpds.values():
    ans = ans*comb(n+i-1,i)%mod

print(ans)

Submission status: Accepted

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


def prime_factorization(n):
    table = []
    for x in range(2, int(n**0.5)+2):
        while n % x == 0:
            table.append(x)
            n //= x
    if n > 1:
        table.append(n)
    return table


def nHk(n, k):
    value = 1
    nk = n + k - 1
    k = min(nk-k, k)
    for i in range(k):
        value = (value * nk) % mod
        nk -= 1
    for x in range(1, k + 1):
        value = (value * pow(x, mod-2, mod)) % mod

    return value


C = Counter(prime_factorization(M))
ans = 1
for v in C.values():
    ans = ans * nHk(N, v) % mod

print(ans)

Submission status: Accepted

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

mod = 10**9 + 7

b = []

c = int(math.sqrt(m))
for i in range(2, c+2):
    count = 0
    while m % i == 0:
        count += 1
        m = m // i
    b.append(count)
if m > 1:
    b.append(1)

fac = [1, 1]
inv = [1, 1]
finv = [1, 1]
for i in range(2, n + max(b)+3):
    fac.append(fac[i-1] * i % mod)
    inv.append(mod - inv[mod%i] * (mod//i) % mod)
    finv.append(finv[i-1] * inv[i] % mod)

def nck(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

ans = 1
for i in b:
    ans *= nck(n-1+i, i)
    ans %= mod

print(ans)

Submission status: Accepted

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

from collections import Counter
def factorize(n):
    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

fac = [1,1] + [0]*(N+100)
finv = [1,1] + [0]*(N+100)
inv = [0,1] + [0]*(N+100)
for i in range(2,N+102):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

def ncr(n,r):
    if n < r: return 0
    if n < 0 or r < 0: return 0
    return fac[n] * (finv[r] * finv[n-r] % MOD) % MOD

ans = 1
facs = factorize(M)
for v in facs.values():
    ans *= ncr(N+v-1,v)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
import math

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

mod=10**9+7

yak=[]

p=1
ind=0
for i in range(2,int(m**0.5)+1):
    if m%i==0 :
        yak.append(0)
        while m%i==0 :
            m=m//i
            yak[ind]+=1
            p=0
        ind+=1

if m!=1 :
    yak.append(1)


ka=[1] # 階乗(mod)のリスト
for i in range(1,10**5*2):
    ka.append((ka[i-1]*i)%mod)

def inv(x): # mod上のxの逆数を求める関数（フェルマーの小定理）
    res=1
    k=mod-2
    y=x
    while k>0 :
        if k%2 == 1 :
            res = (res*y) % mod
        y = (y*y) % mod
        k //= 2
    return res

def modcomb(n,k): # mod上でのコンビネーションを求める関数(nCk)
    a=ka[n]
    b=ka[n-k]
    c=ka[k]

    bc=(b*c)%mod

    return a*inv(bc)%mod



ans=1

for i in range(len(yak)):
    if yak[i]>0 :
        n=nn+yak[i]-1
        k=yak[i]

        ans=(ans*modcomb(n,k))%mod

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
pem=1
if m==1:
    print(1)
def fctr2(n): #それぞれの素因数の指数だけ出力
    f=[]
    c=0
    r=int(n**0.5)
    for i in range(2,r+2):
        while n%i==0:
            c+=1
            n=n//i
        if c!=0:
            f.append(c)
            c=0
    if n!=1:
        f.append(1)
    return f

mod=10**9+7
fuc=[1]
def fucfun(n):
    for i in range(1,n):
        e=fuc[i-1]*i
        fuc.append(e%mod)
def com(n,k):
    com=(fuc[n]%mod)*pow(fuc[k],mod-2,mod)*pow(fuc[n-k],mod-2,mod)
    return com
f=fctr2(m)
if m!=1:
    a=max(f)+n
    fucfun(a)
    s=1
    for i in range(len(f)):
        t=com(f[i]+n-1,f[i])
        s=(s*t)%mod
    print(s)

Submission status: Accepted

Solution code:
import math
n,m = map(int, input().split())
mod = 1000000007
fact = [1]*(n+10000+1)
rfact = [1]*(n+10000+1)
for i in range(n+10000):
    fact[i+1] = rr = ((i+1) * fact[i]) % mod
    rfact[i+1] = pow(rr, mod-2, mod)
def comb(N, K,mod):
    return fact[N] * rfact[K] * rfact[N-K] % mod
def make_prime_list_2(num):
    if num < 2:
        return []

    # 0のものは素数じゃないとする
    prime_list = [i for i in range(num + 1)]
    prime_list[1] = 0 # 1は素数ではない
    num_sqrt = math.sqrt(num)

    for prime in prime_list:
        if prime == 0:
            continue
        if prime > num_sqrt:
            break

        for non_prime in range(2 * prime, num, prime):
            prime_list[non_prime] = 0

    return [prime for prime in prime_list if prime != 0]
def prime_factorization_2(num):
    if num <= 1:
        print(1)
        exit()
        return False
    else:
        num_sqrt = math.floor(math.sqrt(num))
        prime_list = make_prime_list_2(num_sqrt)

        dict_counter = {}
        for prime in prime_list:
            while num % prime == 0:
                if prime in dict_counter:
                    dict_counter[prime] += 1
                else:
                    dict_counter[prime] = 1
                num //= prime
        if num != 1:
            if num in dict_counter:
                dict_counter[num] += 1
            else:
                dict_counter[num] = 1

        return dict_counter
x = prime_factorization_2(m)
x = list(x.values())
ans = 1
for i in x:
  ans*= comb(i+n-1,i,mod)
  ans %=mod
print(ans)

Submission status: Accepted

Solution code:
# coding:utf-8

INF = float('inf')
MOD = 10 ** 9 + 7


def inpl(): return list(map(int, input().split()))


# aのp乗を求めるアルゴリズム
# MOD版
# O(logp)
def pow_mod(a, p):
    if p == 0: return 1
    if p % 2 == 0:
        half_p = p // 2
        half = pow_mod(a, half_p)

        return half * half % MOD
    else:
        return a * pow_mod(a, p - 1) % MOD


# 組み合わせnCrを求めるアルゴリズム
# 逆元を使って計算
# MOD版
def cmb_mod(n, r):
    # 5C3 -> 5C2
    if r > n - r: return cmb_mod(n, n - r)
    ans_mul = 1
    ans_div = 1
    for i in range(r):
        ans_mul *= n - i
        ans_div *= i + 1
        ans_mul %= MOD
        ans_div %= MOD

    # ans_mul / ans_divをしたい
    # ans_divの逆元を使って求める
    ans = ans_mul * pow_mod(ans_div, MOD - 2) % MOD
    return ans


N, M = inpl()
ans = 1
i = 2
while i * i <= M:
    if M % i == 0:
        cnt = 0
        while M % i == 0:
            cnt += 1
            M //= i
        ans *= cmb_mod(N - 1 + cnt, cnt)
        ans %= MOD
    i += 1

if M != 1:
    ans *= cmb_mod(N - 1 + 1, 1)
    ans %= MOD
print(ans)

Submission status: Accepted

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

#x以下の素数の列挙   
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#素数でないものは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]

#素因数分解
DICT=dict()
i=0
while M!=1:
    if M%Primes[i]==0:
        DICT[i]=DICT.get(i,0)+1
        M=M//Primes[i]
    elif i<len(Primes)-1:
        i+=1
    else:
        DICT[M]=1
        M=1

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

    return ANS%mod


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

print(ANS)

Submission status: Accepted

Solution code:
import math
def comb(n,m):
    p=1;q=1
    for i in range(m):p*=i+1;q*=n-i
    return q//p
n,m=map(int,input().split())
q=int(math.sqrt(m))
l=[True]*q
l[0]=False
for i in range(2,q+1):
    if l[i-1]:
        j=2
        while i*j<=q:l[i*j-1]=False;j+=1
p={}
for i in {(i+1)for i in range(q)if l[i]}:
    while 1:
        if m%i==0:p[i]=1+p[i]if i in p.keys()else 1;m//=i
        else:break
if m>1:p[m]=1+p[m]if m in p.keys()else 1
r=1
for v in p.values():r*=comb(v+n-1,v)
print(r%1000000007)

Submission status: Accepted

Solution code:
import collections
def com(x,y):
    y=min(y,x-y)
    a=1
    for i in range(x,x-y,-1):
        a*=i
    b=1
    for i in range(1,y+1):
        b*=i
    return a//b
n,m=map(int,input().split())
y=[]
i=2
z=m
while(i*i<=m):
    if m%i:
        i+=1
    else:
        m//=i
        y.append(i)
if m>1:
    y.append(m)
c=collections.Counter(y).values()
ans=1
mod=10**9+7
for t in c:
    ans*=com(t+n-1,t)
    ans%=mod
print(ans)

Submission status: Accepted

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

MOD = 10**9+7

def factorize(n):
    from math import sqrt
    m = int(sqrt(n)) + 1
    p = [True] * m
    result = {}
    for x in range(2, m):
        if p[x]:
            p[x * 2::x] = [False] * ((m - 1) // x - 1)
            i = 0
            while 1:
                d, q = divmod(n, x)
                if q == 0:
                    n = d
                    i += 1
                    result[x] = i
                else:
                    break
    if n > 1:
        result[n] = 1
    return result

def C(x, y):
    r = 1
    s = 1
    for i in range(y):
        r *= (x - i)
    for i in range(y):
        s *= (i + 1)
    return (r // s) % MOD

result = 1

for x in factorize(M).values():
    result = result * C(N + x - 1, x) % MOD

print(result)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
import math

s_in = lambda: stdin.readline()[:-1] # s = s_in()
d_in = lambda: int(stdin.readline()) # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split())) # List = ds_in()

N, M = ds_in()
MOD = 10**9 + 7

def factorize(n):
    if n == 1:
        return []
    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, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct

fct = factorize(M)

def recursive_square(n, m, p):
    """ n**p (mod m) """
    if p == 0:
        return 1 % m
    if p % 2 == 0:
        root = recursive_square(n, m, p//2) % m 
        return (root ** 2) % m
    else:
        return ((n % m) * recursive_square(n, m, p-1)) % m

Inv = dict([[1,1]]) # 逆元

# 組み合わせ
def combination(n, r):
    val = 1
    for i in range(1, r+1):
        if i not in Inv.keys():
            Inv[i] = recursive_square(i, MOD, MOD-2)
        val = (((val * (n-i+1)) % MOD) * Inv[i]) % MOD
    return val

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

Submission status: Accepted

Solution code:
import math
 
N,M=map(int,raw_input().split())
m=int(math.sqrt(M))+2
 
mod=10**9+7
fact, inv_fact = [1], [1]
fact_tmp = 1
for i in range(1, 10**5+10000):
    fact_tmp *= i
    fact_tmp %= mod
    fact.append(fact_tmp)
    inv_fact.append(pow(fact_tmp, mod-2, mod))
 
 
def ncr(n,r):
	if n < 0 or r < 0 or n < r:
		return 0
	else:
		return (fact[n] * inv_fact[r] * inv_fact[n-r]) %mod
 
ans=1
 
for i in range(2, m):
	cnt=0
	while M%i==0:
		M/=i
		cnt+=1
	ans*=ncr(N+cnt-1,cnt)
	ans%=mod
 
if M!=1:
	ans*=N
	ans%=mod

print ans

Submission status: Accepted

Solution code:
def d_factorization(N, M):
    if M == 1:
        return 1

    def prime_factorization_power_list(n):
        i = 2
        table = {}
        while i**2 <= n:
            table[i] = 0
            while n % i == 0:
                table[i] += 1
                n //= i
            if table[i] == 0:
                table.pop(i)
            i += 1
        if n > 1:
            table[n] = 1
        return table

    MOD = 10**9 + 7
    prime_m = prime_factorization_power_list(M)
    b_max = max(prime_m.values())  # 素因数分解の指数の最大値
    # フェルマーの小定理による組合せの計算
    factorial = [1] * (b_max + N)  # (b_i + N - 1)!を計算するため。0!も入れておく
    for k in range(1, b_max + N - 1):
        factorial[k + 1] = (factorial[k] * (k + 1)) % MOD
    # k!のmod 10**9+7における逆元を計算
    fact_inv = [1] * (b_max + N)
    fact_inv[b_max + N - 1] = pow(factorial[b_max + N - 1], MOD - 2, MOD)
    for k in range(b_max + N - 1, 0, -1):
        fact_inv[k - 1] = (fact_inv[k] * k) % MOD

    def nCr(n, r, M):
        if n < 0 or r < 0 or n < r:
            return 0
        else:
            return (factorial[n] * fact_inv[r] * fact_inv[n - r]) % M

    ans = 1
    for b in prime_m.values():
        ans = (ans * nCr(b + N - 1, b, MOD)) % MOD

    return ans

N, M = [int(i) for i in input().split()]
print(d_factorization(N, M))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
bigp = 10**9+7
L = []
p, power = 2, 0
K = M
while p*p <= K:
    while K%p == 0:
        K = K//p
        power += 1
    if power > 0:
        L.append([p, power])
    if p == 2:
        p += 1
    else:
        p += 2
    power = 0
if K > 1:
    L.append([K, 1])


ans = 1
def ModComb(n, r, p):
    N = n%p
    R = r%p
    if N<R:
        return 0
    if N < 2*R:
        R = N-R
    if R == 0:
        return 1
    else:
        return (n*pow(r, p-2, p))%p*ModComb(n-1, r-1, p)


for i in range(len(L)):
    power = L[i][1]
    ans *= ModComb(N+power-1, power, bigp)
    ans %= bigp

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
import copy

def power_func(a,b,p):
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p


class comb_calclator():
    def __init__(self, N, p):
        self.N = N
        self.p = p
        self.frac_N = [0 for i in range(N + 1)]
        self.frac_N[0] = 1L
        self.comb_N = {}
        for i in range(1, N + 1):
            self.frac_N[i] = (self.frac_N[i - 1] * i ) % p

    def comb(self, n, r):
        if n<0 or r<0 or n<r: return 0
        if n==0 or r==0: return 1
        if (n, r) in self.comb_N:
            return self.comb_N[(n, r)]
        a = self.frac_N[n]
        b = self.frac_N[r]
        c = self.frac_N[n - r]
        self.comb_N[(n, r)] = (a*power_func(b,self.p-2,self.p)*power_func(c,self.p-2, self.p))% self.p
        self.comb_N[(n, n - r)] = self.comb_N[(n, r)]
        return self.comb_N[(n, r)]


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

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] = [int(input_raw[0]), int(input_raw[1])]

    prime_table = prime_decomposition(M)
    primes = {}
    for p in prime_table:
        if p in primes:
            primes[p] += 1
        else:
            primes[p] = 1

    max_num = 0
    for p in primes:
        max_num = max(max_num, primes[p])

    cmb = comb_calclator(max_num + N, int(1e+9) + 7)
    count = 1
    for p in primes:
        b = primes[p]
        count = (count * cmb.comb(b + N - 1, b))%(int(1e+9) + 7)


    print count



if __name__ == '__main__':
    main()