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 itertools

def factors(n):
    f = 2
    increments = itertools.chain([1,2,2], itertools.cycle([4,2,4,2,4,6,2,6]))
    for incr in increments:
        if f*f > n:
            break
        while n % f == 0:
            yield f
            n //= f
        f += incr
    if n > 1:
        yield n

def matome(ls):
    new = []
    num = []
    for l in ls:
        if not l in new:
            new.append(l)
            num.append(1)
        else:
            num[new.index(l)] += 1
    return num

def mod_combination(n, k, mod):
    # nCk (mod m)
    def mod_permutation(n, k, mod):
        if n<=k:
            return 1
        else:
            return (n * mod_permutation(n-1,k,mod))%mod

    def mod_inv_permutation(k, mod):
        k, mod = int(k), int(mod)
        if k<=1:
            return 1
        else:
            return (pow(k,mod-2,mod) * mod_inv_permutation(k-1, mod))%mod

    return (mod_permutation(n,n-k,mod) * mod_inv_permutation(k, mod))%mod

def main():
    n,m = map(int, input().split())
    l = list(factors(m))
    y = matome(l)
    x = 1
    for i in y:
        x *= mod_combination(n+i-1,i,10**9+7)
        x = x%(10**9+7)
    print(x)
if __name__ == '__main__':
    main()

Submission status: Accepted

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

def factorized(M):
    d = 2
    f = []
    while d <= M:
        count = 0
        while M % d == 0:
            M //= d
            count += 1
        if count > 0:
            f.append(count)
        d += 1
        if d < M and d * d > M:
            d = M
    return f

def tetra(n, m):
    x = 1
    for y in range(1, n):
        x = x * (m + y - 1) // y
    return x

x = 1
for f in factorized(M):
    x *= tetra(N, f + 1)
    x %= 10 ** 9 + 7

print(x)

Submission status: Accepted

Solution code:
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]


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

s=primes(10**5)
t=[]

for i in range(len(s)):
    if m%s[i]==0:
        t.append(1)
        m//=s[i]
    while True:
        if m % s[i] == 0:
            t[-1]+=1
            m //= s[i]
        else:
            break
if m!=1:
    t.append(1)

ans=1
for i in range(len(t)):
    for j in range(t[i]):
        ans*=j+n
    for j in range(t[i]):
        ans//=j+1
    ans%=(10**9+7)

print(int(ans))

Submission status: Accepted

Solution code:
import sys

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

factor = {}
tmp = 2
while(M // tmp >= 1):
    if(M % tmp != 0):
        if(tmp == 2):
            tmp += 1
        elif(M // tmp < tmp):
            tmp = M
        else:
            tmp += 2
        continue

    M = M // tmp
    factor[tmp] = factor.get(tmp, 0) + 1

if(factor == {}):
    print(1)
    sys.exit()

ans = 1
max_a = 7 + 10 ** 9
max_value = max(list(factor.values()))
aho = {0: 1}
fact = {0: 1}
abc = {}
for i in range(1, max_value + 1):
    # print(i)
    aho[i] = ((aho[i - 1] * (i + N - 1)))
    fact[i] = (fact[i - 1] * i)
    abc[i] = (aho[i] // fact[i]) % max_a


# print(factor)
# print(aho, fact)
for i in factor.values():
    # print(i)
    ans = (ans * abc[i]) % max_a
print(ans)

Submission status: Accepted

Solution code:
import math
N,M=map(int,input().split())
def primecheck(K):
    A=int(math.sqrt(K))+1
    for i in range(2,A+1):
        if K%i==0:
            return i
    return 1
D=dict()
while(True):
    X=int(math.sqrt(M))+1
    for i in range(2,X+1):
        if M%i==0:
            while(True):
                if i in D:
                    D[i]+=1
                else:
                    D[i]=1
                M=M//i
                if M%i!=0:
                    break
    j=primecheck(M)
    if j==1:
        if M==1:
            break
        D[M]=1
        break
    else:
        if j in D:
            D[j]=1
        else:
            D[j]+=1
P=10**9+7
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
def inv(x):
    return egcd(x,P)[0]
Y=N+100
Fact=[0 for i in range(Y+1)]
Finv=[0 for i in range(Y+1)]
Fact[0]=1
Finv[0]=1
for i in range(Y):
    Fact[i+1]=(Fact[i]*(i+1))%P
    Finv[i+1]=inv(Fact[i+1])%P
def C(n,k):
    return (Fact[n]*(Finv[k]*Finv[n-k])%P)%P
ans=1
for p in D:
    e=D[p]
    ans=ans*C(e+N-1,N-1)
    ans=ans%P
print(ans)

Submission status: Accepted

Solution code:
num = (10 ** 9) + 7

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

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

prime_upper = int(m ** (1/2) + 50)
prime_dict = {}

check = [False] * prime_upper
prime = [2]

while m % 2 == 0:
    m //= 2
    if not 2 in prime_dict.keys():
        prime_dict[2] = 0
    prime_dict[2] += 1

for j in range(2, prime_upper, 2):
    check[j] = True

for i in range(3, prime_upper, 2):
    if not check[i]:
        prime.append(i)
        while m % i == 0:
            m //= i
            if not i in prime_dict.keys():
                prime_dict[i] = 0
            prime_dict[i] += 1

        for j in range(i, prime_upper, i):
            check[j] = True

if len(prime_dict.values()) != 0:
    value_max = max(prime_dict.values())
    com2 = [[0] * (value_max + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, value_max + 1):
            if i == 1:
                com2[i][j] = 1
            elif j == 1:
                com2[i][j] = i
            else:
                com2[i][j] = (com2[i][j - 1] + com2[i - 1][j]) % num
    if m != 1:
        ans = n
    else:
        ans = 1
    for key, value in prime_dict.items():
        ans = (ans * com2[n][value]) % num
    print(ans)
else:
    print(n)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import heapq
import itertools
import math
from collections import defaultdict

def factorization(m, flag=0):
    m0 = m
    hq = []
    F = defaultdict(int)
    for n in itertools.count(2) if flag else range(2,math.ceil(math.sqrt(m))+5):

        while hq and hq[0][0] == n:
            heapq.heapreplace(hq,(sum(hq[0]),hq[0][1]))
            if hq[0][0] > n:break
        else:
            while m > 1:
                if m%n:
                    break
                else:
                    m //= n
                    F[n] += 1
            hq.append((n*n,n))
            if m == 1:
                return F
    if not F or m > 1:
        F[m] += 1
    return F


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

def solve():
    N, M = map(int, input().split())
    F = factorization(M)
    res = 1
    for n in F.values():
        res *= cmb(N+n-1, n)
    res %= (10**9+7)
    return str(res)

if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
from math import sqrt, ceil, factorial
from collections import defaultdict


def prime_factors(n):
    i = 2
    factors = defaultdict(int)
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors[i] += 1
    if n > 1:
        factors[n] += 1
    return factors


N, M = [int(elem) for elem in input().split(' ')]

# 素因数分解
prime_numbers = prime_factors(M)
sum = 1
fac_N_m1 = factorial(N - 1)

for value in prime_numbers.values():
    bunshi = 1
    saisho = value + N - 1
    for _ in range(value):
        bunshi *= saisho
        saisho -= 1
    sum *= (bunshi // factorial(value))
print(sum % (10**9 + 7))

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
def usage():
    
    fct = factorize(M)
    lis = []
    for t in fct:
      lis.append(t[1])
    ans = 1
    for nums in lis:
      ans = (ans*cmb(N+nums-1,N-1,10**9+7))%(10**9+7)
    print(ans)
    
def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct
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, 10*N ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
usage()

Submission status: Accepted

Solution code:
import math

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

qq = {}
for i in range(2, int(math.sqrt(M)) + 2):
    while M % i == 0:
        if i in qq:
            qq[i] += 1
        else:
            qq[i] = 1
        M //= i
if M > 1:
    qq[M] = 1

def pow(n, r):
    if r == 0:
        return 1
    if r % 2 == 0:
        return pow(n * n % mod, r // 2) % mod
    else:
        return n * pow(n, r - 1) % mod

ans = 1
a = 0

for r in qq.values():
    C = 1
    for i in range(r):
        C = C * (N + r - 1- i) * pow(i + 1, mod - 2) % mod
    a += r
    ans = ans * C % mod

print(ans)

Submission status: Accepted

Solution code:
import math
import collections
def trial_division_sqrt(n):

    prime_count = collections.Counter()

    for i in range(2, int(math.sqrt(n)) + 2):
        while n % i == 0:
            n /= i
            prime_count[i] += 1
    if n > 1:
        prime_count[n] += 1

    return prime_count
def pc(n, r):
    return math.factorial(n) // (math.factorial(n - r)  * math.factorial(r))
nCr = {}
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;
s=0
x,N = map(int,input().split())

li = trial_division_sqrt(N)
li = li.most_common()
ans = 1
for i in range(0, len(li)):
    ans *= cmb(li[i][1] + x-1, x-1)
print(ans % (pow(10, 9)+7))

Submission status: Accepted

Solution code:
from collections import Counter
from math import factorial
Q = 10**9+7
def primes(n):
    primfac = [0]
    d = 2
    while d*d <= n:
        while n%d == 0:
            primfac[-1] += 1
            n //= d
        d += 1
        if primfac[-1] != 0:
            primfac.append(0)
    if n > 1:
        if primfac[-1] == 0:
            primfac[-1] += 1
        else:
            primfac.append(1)
    return primfac
def combination(a,b):
    return ( (factorial(a)//factorial(b))//factorial(a-b))%Q
N, M = map( int, input().split())
C = primes(M)
ans = 1
if N == 1:
    print(1)
else:
    for x in C:
        ans = (ans * combination(x+N-1,N-1))%Q
    print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np

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

def soin(a):
    fa = []
    i = 2
    d = a
    last = 1
    while d>1:
        if d % i == 0:
            if last == i:
                fa[-1][1]=fa[-1][1]+1
            else:
                fa.append([i,1])
            d=d//i
            last = i
        else:
            i += 1
        if i * i > a:
            fa.append([a,1])
            break

    return(fa)

#print(soin(n))
q = soin(m)
answer = 1

for i in q:
#    print(i,i[1])
    r = i[1]
    a = 1
    for j in range(n,n+r):
        a = a * j
    for j in range(r):
        a = a // (j+1)
    answer = answer * a % (10**9+7)

print(answer)

Submission status: Accepted

Solution code:
from collections import Counter
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 #出力の制限
N = 10**5+1000
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

n,m=map(int, input().split())
mb=[]
while m>1:
    for i in range(2,int(m**0.5)+1):
        if m%i==0:
            mb.append(i)
            m//=i
            break
    else:
        mb.append(m)
        m//=m
mb2=Counter(mb)
    
mblist=list()
for i in mb2:
    a = cmb(mb2[i]+n-1,mb2[i],mod)
    mblist.append(a)
ans=1
for i in mblist:
    ans=(ans*i)%mod
print(ans)

Submission status: Accepted

Solution code:
import math
N,M=map(int,input().split())
def primecheck(K):
    A=int(math.sqrt(K))+1
    for i in range(2,A+1):
        if K%i==0:
            return i
    return 1
D=dict()
while(True):
    X=int(math.sqrt(M))+1
    for i in range(2,X+1):
        if M%i==0:
            while(True):
                if i in D:
                    D[i]+=1
                else:
                    D[i]=1
                M=M//i
                if M%i!=0:
                    break
    j=primecheck(M)
    if j==1:
        if M==1:
            break
        D[M]=1
        break
    else:
        if j in D:
            D[j]=1
        else:
            D[j]+=1
P=10**9+7
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
def inv(x):
    return egcd(x,P)[0]
Y=2*10**5
Fact=[0 for i in range(Y+1)]
Finv=[0 for i in range(Y+1)]
Fact[0]=1
Finv[0]=1
for i in range(Y):
    Fact[i+1]=(Fact[i]*(i+1))%P
    Finv[i+1]=inv(Fact[i+1])%P
def C(n,k):
    return (Fact[n]*(Finv[k]*Finv[n-k])%P)%P
ans=1
for p in D:
    e=D[p]
    ans=ans*C(e+N-1,N-1)
    ans=ans%P
print(ans)

Submission status: Accepted

Solution code:
from math import factorial, sqrt

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


ans = 1

if m != 1:
    factorization = {}
    while True:
        for i in range (2, int(sqrt(m))+1):
            if m % i == 0:
                if i in factorization:
                    factorization[i] += 1
                else:
                    factorization[i] = 1
                m = m // i
                break
        else:
            if m in factorization:
                    factorization[m] += 1
            else:
                factorization[m] = 1
            break


    for i in factorization.keys():
        k = factorization[i]

        num = 1
        for i in range(k):
            num *= (n+k-1-i)
        num //= factorial(k)
        ans *= num % (10**9+7)
        ans = ans % (10**9+7)



print(ans)

Submission status: Accepted

Solution code:
from math import factorial

nm = input().split()
n = int(nm[0])
m = int(nm[1])

f = []

i = 2
j = 0
while (m > 1) and i<=m:
    while m%i == 0:
        m /= i
        j += 1
    if j >= 1:
        f.append(j)
    i += 1
    j = 0

        
ans = 1

for k in f:
    if k > 0:
        ans *= factorial(n+k-1) // (factorial(k) * factorial(n-1))
    
print(int(ans) % (10**9+7))

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string

def factors_nojit(n):
    gaps = [1,2,2,4,2,4,2,4,6,2,6]
    length, cycle = 11, 3
    f, fs, nxt = 2, [], 0
    while f * f <= n:
        while n % f == 0:
            fs.append(f)
            n0 = n
            n //= f
        f += gaps[nxt]
        nxt += 1
        if nxt == length:
            nxt = cycle
    if n > 1: fs.append(n)
    return fs

MAX = 10**5 + 100
mod = 10**9+7

fac = [1]*(MAX+1)
for i in range(1,MAX+1):
    fac[i] = (fac[i-1]*i)%mod

rev_m = [1]*(MAX+1)
rev_m[MAX] = pow(fac[MAX],mod-2,mod)
for i in range(MAX,0,-1):
    rev_m[i-1] = (rev_m[i]*i)%mod

def Comb(n,k):#nCk
    return (fac[n]*rev_m[k]*rev_m[n-k])%mod

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

fs =  factors_nojit(M)
fs.sort()

dd = defaultdict(int)
ed = []
for f in fs:
    if dd[f] == 0:
        ed.append(f)
    dd[f] += 1

ans =1
for e in ed:
  k = dd[e]
  ans *= Comb(k+N-1,k)
  ans %= mod

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

N, M = map(int, raw_input().split())
m = {}
for i in range(2, 100000):
    if M % i == 0:
        m[i] = 0
    while M % i == 0:
        m[i] += 1
        M /= i

if M > 1:
    m[M] = 1

ans = 1
MOD = 10 ** 9 + 7

for p in m:
    S = 1
    for i in range(1, m[p] + 1):
        S *= N + m[p] - i
        S /= i
    ans *= S
    ans %= MOD

print ans

Submission status: Accepted

Solution code:
import math
 
def prime_factors(n):
	i = 2
	factors = []
	while i * i <= n:
		if n % i:
			i += 1
		else:
			n //= i
			factors.append(i)
	if n > 1:
		factors.append(n)
	return factors
	

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		g, y, x = egcd(b % a, a)
		return (g, x - (b // a) * y, y)
		
def modinv(a, m):
	g, x, y = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m
		
def factorial(n):
	num = 1
	while n >= 1:
		num = (num * n) % 1000000007
		n = n - 1
	return num
	   
a = input().split()
a = [int(i) for i in a]
 
num = dict()
for i in prime_factors(a[1]):
	if i not in num:
		num[i] = 1
	else:
		num[i] += 1
		
ans = 1
for j in num.values():
	ans *= factorial(j + a[0] - 1)
	ans %= (10**9 + 7)
	inv = modinv((factorial(a[0] - 1)* factorial(j)), 1000000007)
	ans *= inv
	ans %= (10**9 + 7)
	
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import math
from math import factorial

# K = int(input())
# N, K = map(int, input().split())
# A = list(map(int, input().split()))
# S = input() # String

mod = 1000000000 + 7

fact_table = dict()

def dupcomb(n, k, p):
    return comb(n+k-1, k, p)

def comb(n,k,p):
    if n<0 or k<0 or n<k: return 0
    if n==0 or k==0: return 1

    if n in fact_table:
        a = fact_table[n]
    else:
        a=factorial(n) %p
        fact_table[n] = a

    if k in fact_table:
        b = fact_table[k]
    else:
        b=factorial(k) %p
        fact_table[k] = b
        
    if n-k in fact_table:
        c = fact_table[n-k]
    else:
        c=factorial(n-k) %p
        fact_table[n-k] = c
        
    return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p

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


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

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

primes = factorize(M)

count = 1

fk_save = dict()

for pair in primes:
    k = pair[1]
    # print('k=', k)

    if k in fk_save:
        fk = fk_save[k]
    else:
        fk = dupcomb(N, k, mod)
        fk_save[k] = fk
    # print('fk=', fk)

    count = (fk * count) % mod
    # print('count=', count)
    
print(count)
# ret = comb(10, 5, mod)
# print(ret)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
prime = [True] * 35001
prime[0] = prime[1] = False
primes = []
for i in range(2, 35001):
  if prime[i]:
    prime[i*2::i] = [False] * ((35000 - i) // i)
    primes.append(i)

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

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

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

numFactors = [0] * len(primes)
while True:
  for i, p in enumerate(primes):
    if M % p == 0:
      numFactors[i] += 1
      M //= p
      break
  else:
    if M > 1:
      # prime
      numFactors.append(1)
    break

ans = 1
for nf in numFactors:
  if nf == 0:
    continue
  ans *= cmb(N+nf-1, nf)
  ans %= mod
print(ans)

Submission status: Accepted

Solution code:
#http://nihaoshijie.hatenadiary.jp/entry/2018/02/03/115759
N,M=map(int,input().split())
P=10**9+7
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
def inv(x):
    return egcd(x,P)[0]
Z=2*10**5
Fact=[0 for i in range(Z+1)]
Finv=[0 for i in range(Z+1)]
Fact[0]=1
Finv[0]=1
for i in range(Z):
    Fact[i+1]=(Fact[i]*(i+1))%P
    Finv[i+1]=inv(Fact[i+1])%P
def C(n,k):
    return (Fact[n]*(Finv[k]*Finv[n-k])%P)%P
def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct
D=factorize(M)
ans=1
for seq in D:
    k=seq[1]
    ans=ans*C(k+N-1,N-1)
    ans=ans%P
print(ans)

Submission status: Accepted

Solution code:
import operator as op
from itertools import groupby
from functools import reduce

NN = 10 ** 9 + 7


def prime_factors(n):
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            yield i
    if n > 1:
        yield n


def ncr(n, r):
    r = min(r, n-r)
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer // denom


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

for k, g in groupby(prime_factors(M)):
    result = result * ncr(len(list(g)) + N - 1, N - 1)
    if result > NN:
        result = result % NN

print(result)

Submission status: Accepted

Solution code:
def mod_combination(n, k, mod):
    # nCk (mod m)
    def mod_permutation(n, k, mod):
        if n<=k:
            return 1
        else:
            return (n * mod_permutation(n-1,k,mod))%mod

    def mod_inv_permutation(k, mod):
        k, mod = int(k), int(mod)
        if k<=1:
            return 1
        else:
            return (pow(k,mod-2,mod) * mod_inv_permutation(k-1, mod))%mod

    return (mod_permutation(n,n-k,mod) * mod_inv_permutation(k, mod))%mod

N, M = map(int, input().split(" "))
X=[]
Y=[]
c=-1
K = 10 ** 9 + 7
i=2
while True:
    if M % i == 0:
        X.append(i)
        Y.append(0)
        c += 1
        while M % i == 0:
            M /= i
            Y[c] += 1

    if i==2:
        i += 1
    else:
        i += 2

    if i>M:
        break

    if i**2>M:
        X.append(M)
        Y.append(1)
        break

ret = 1
for i in Y:
    ret *= mod_combination(i+N-1, i, K)
    ret %= K

print (ret)

Submission status: Accepted

Solution code:
N, M = [int(i) for i in input().split(' ')]
mod = pow(10, 9) + 7
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

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

NNN = (10**5) * 2
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

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

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

xxs = prime_decomposition(M)

result = 1
for xx in xxs:
    result = mul(result, cmb(xx+N-1,xx,mod))
print(result)

Submission status: Accepted

Solution code:
from collections import Counter
from math import sqrt

#f_listとf_r_listの要素数は状況に応じて変えよう

MOD = (10 ** 9) + 7

list_size = 3 * (10 ** 5)

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size - 1):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % MOD)

def power(n, x):
	if x == 1:
		return n
	elif x % 2 == 0:
		return power(int((n * n) % MOD), int(x / 2))
	else:
		return int((n * power(n, x - 1)) % MOD)

f_r_list[-1] = power(f_list[-1], MOD - 2)

for i in range(2, list_size + 1):
	f_r_list[-i] = int((f_r_list[-i + 1] * (list_size + 2 - i)) % MOD)

def comb(n, r):
	if n < r:
		return 0
	elif n == 0 or r == 0 or n == r:
		return 1
	else:
		return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD 

def is_prime(i):
	if i == 1:
		return False
	for j in range(2, int(sqrt(i)) + 1):
		if i % j == 0:
			return False
	return True

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

for i in range(2, int(sqrt(m)) + 1):
	if m % i == 0:
		prime_factor[i] += 1
		m = m // i
		while m % i == 0:
			prime_factor[i] += 1
			m = m // i
	if is_prime(m):
		prime_factor[m] += 1
		break

ans = 1
for i in prime_factor.values():
	ans *= comb(n + i - 1, i)
	ans %= MOD
print(ans)

Submission status: Accepted

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

import sys
sys.setrecursionlimit(10**6)

MOD = 10**9 + 7
F = [M]
for x in range(2, int(sqrt(M))+1):
    if M % x == 0:
        F.append(x)
        if x != M // x:
            F.append(M // x)
F.sort(reverse=1)
L = len(F)
FF = [1]*(L+1)
fact = [1]*100
rfact = [1]*100
for i in range(L):
    FF[i+1] = FF[i] * (N - i) % MOD
for i in range(99):
    fact[i+1] = r = fact[i] * (i+1)
    rfact[i+1] = pow(r, MOD-2, MOD)
memo = {}
def dfs(i, rest, k):
    key = (i, rest, k)
    if i == L:
        if rest > 1:
            return 0
        return FF[k]
    if key in memo:
        return memo[key]
    f = F[i]
    r = dfs(i+1, rest, k)
    c = 0
    while rest % f == 0:
        rest //= f
        c += 1
        r = (r + dfs(i+1, rest, k+c) * rfact[c]) % MOD
    memo[key] = r
    return r
if M == 1:
    print(1)
else:
    print(dfs(0, M, 0))

Submission status: Accepted

Solution code:
def sieve(n):
    '''
    :param n:
    :return: n以下の素数のリストを返す
    エラトステネスの篩→O(n log log n)
    '''
    prime = []
    is_prime = [True] * (n + 1) #is_prime[i] = Trueならiは素数
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n+1):
        if is_prime[i]:
            prime.append(i)
            for j in range(2 * i, n + 1, i):
                is_prime[j] = False
    return prime

dp_memo = [0] * 50
def f(x):
    #f(x) = (x + N -1) C (N - 1)
    if dp_memo[x] > 0:
        return dp_memo[x]
    elif x == 0:
        return 1
    else:
        return (f(x - 1) * (x + N - 1)) // x

N, M = map(int, input().split())
P = sieve(4 * 10 ** 4)
index = []
i = 0
while M > 1 and i < len(P):
    cnt = 0
    while M % P[i] == 0:
        cnt += 1
        M //= P[i]
    i += 1
    if cnt > 0:
        index.append(cnt)

if M > 1:
    index.append(1)

ans = 1
for i in index:
    ans = ans * f(i) % (10 ** 9 + 7)

print(ans)

Submission status: Accepted

Solution code:
ai = lambda: list(map(int, input().split()))
ai_ = lambda: [int(x) - 1 for x in input().split()]

n, m = ai()


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


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

ans = 1
f = factorize(m)
for p,num in f:
    ans *= nCb(num+n-1,num)
    ans %= 10**9+7

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

X = 10**9+7
N,M = list(map(int,input().split()))
def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct

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])%X

    return result%X


ans = 1
for val,dupes in factorize(M):
    ans *= cmb(N+dupes-1,N-1)
    ans = ans % X
print(ans%X)

Submission status: Accepted

Solution code:
from collections import defaultdict


def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return factorials, invs


def prime_factorize(n):
    f = defaultdict(lambda: 0)
    f[2] = len(bin(n & -n)) - 3
    i = 3
    k = n >> f[2]
    while k > 1:
        while True:
            d, m = divmod(k, i)
            if m == 0:
                f[i] += 1
                k = d
            else:
                break
        i += 2
    return f


MOD = 1000000007
n, m = map(int, input().split())
pf = prime_factorize(m)
mx = max(pf.values())
f, r = prepare(n + mx, MOD)
ans = 1
for p, e in pf.items():
    ans *= f[n + e - 1]
    ans %= MOD
    ans *= r[n - 1]
    ans %= MOD
    ans *= r[e]
    ans %= MOD
print(ans)