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:
MOD = int(1e9+7)
f = {}
f[0] = 1
for i in range(1, 100100):
    f[i] = f[i - 1] * i
    f[i] %= MOD

def mod_pow(x, y):
    if y == 0:
        return 1
    res = mod_pow(x * x % MOD, y // 2)
    if y & 1 == 1:
        res = res * x
    return res

def inverse(x):
    return mod_pow(x, MOD - 2)

def cmb(n, r):
    return f[n] * inverse(f[r] * f[n - r] % MOD)

n, m = map(int, input().split())
ans = 1
t = 2
while m >= t ** 2:
    cnt = 0
    while m % t == 0:
        m //= t
        cnt += 1
    if cnt > 0:
        ans *= cmb(n + cnt - 1, cnt) % MOD
        ans %= MOD
    t += 1
if m > 1:
    ans *= n
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
def cmb(n,r):
    r=min(r,n-r)
    result=1
    for i in range(n-r+1,n+1):
        result*=i
    for i in range(1,r+1):
        result//=i
    return result

def factorize(n):
    i=2
    result={}
    while True:
        if i**2>n:
            break
        count=0
        while n%i==0:
            n//=i
            count+= 1
        if count!=0:
            result[i]=count
        i+=1
    if n>1:
        result[n]=1
    return result


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

r = 1
for i,j in l.items():
    r *= cmb(j+N-1,j)%(10**9+7)
    r %= (10**9+7)
print(r)

Submission status: Accepted

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
# FROM: https://atcoder.jp/contests/abc110/submissions/3364130
# N,M = map(int, input().split())
from collections import defaultdict
import math

N,m=map(int,input().split())
primelist = defaultdict(int)
MOD = 10**9+7

for i in range(2,10**5):
    s = 0
    while m%i == 0 and m > 1:
        m = m //i
        s += 1
    if s>0:
        primelist[i] = s

if m>1: # residual 
    primelist[10**9] = 1 # only this divisor cannot be detected above

def comb(n,k):
    res = 1
    for i in range(1,1+k):
        res = res * (n-i+1)
        res %= MOD
        res *= pow(i, MOD-2, MOD)
    return res
ans = 1
# print(primelist.items())
for l,t in primelist.items(): # for defaultdict
    ans *= comb(N-1+t, t)
    ans %= MOD
print(ans)

Submission status: Accepted

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

def combination(n,r):
    r=min(r,n-r)
    result=1
    for i in range(n-r+1,n+1):
        result*=i
    for i in range(1,r+1):
        result//=i
    return result

def factorize(n):
    i=2
    result={}
    while True:
        if i**2>n:
            break
        count=0
        while n%i==0:
            n//=i
            count+= 1
        if count!=0:
            result[i]=count
        i+=1
    if n>1:
        result[n]=1
    return result

ans=1
mod=10**9+7
f=factorize(m)
for i in f.values():
    ci=combination(i+n-1,i)%mod
    ans=ans*ci%mod
print(ans)

Submission status: Accepted

Solution code:
import math
mod = 1000000007
N,M = list(map(int,input().strip().split()))
l = []

ans = 1
cnt = 0
while  M%2 == 0:
  M //= 2
  cnt += 1
l.append(cnt)
cnt = 0

i = 3
while i**2 <= M:
  cnt = 0
  while M%i == 0:
    M //= i
    cnt += 1
  if cnt != 0:
    l.append(cnt)
    cnt = 0
  i += 2
if M != 1:
    l.append(1)

for i in l:
  for j in range(i):
    ans = ans*(N+j)//(j+1)

print(ans%mod)

Submission status: Accepted

Solution code:
import math
mod = 1000000007
N,M = list(map(int,input().strip().split()))
l = []

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

def C(n, r):
  return P(n, r)//math.factorial(r)

ans = 1
cnt = 0
while  M%2 == 0:
  M //= 2
  cnt += 1
l.append(cnt)
cnt = 0

i = 3
while i**2 <= M:
  cnt = 0
  while M%i == 0:
    M //= i
    cnt += 1
  if cnt != 0:
    l.append(cnt)
    cnt = 0
  i += 2
if M != 1:
    l.append(1)

for i in l:
  for j in range(i):
    ans = ans*(N+j)//(j+1)

print(ans%mod)

Submission status: Accepted

Solution code:
import scipy.misc
import math

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

M = m
lst, count = [],[]

for i in range(2,int(math.sqrt(m))+1):
    while M % i == 0:
        M = M // i
        if i not in lst:
            count.append(1)
            lst.append(i)
        else:
            count[-1] += 1
if M > 1:
    lst.append(M)
    count.append(1)       

ans = 1
for i in count:
    ans = ans * scipy.misc.comb(i+n-1,i, exact=1)
    ans = ans % (10**9+7) 

print(int(ans))

Submission status: Accepted

Solution code:
import scipy.misc
import math

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

M = m
lst, count = [],[]
if M == 1:
    print(1)
else:
    for i in range(2,int(math.sqrt(m))+1):
        while M % i == 0:
            M = M // i
            if i not in lst:
                count.append(1)
                lst.append(i)
            else:
                count[-1] += 1
    if M > 1:
        lst.append(M)
        count.append(1)       

    ans = 1
    for i in count:
        ans = ans * scipy.misc.comb(i+n-1,i, exact=1)
        ans = ans % (10**9+7) 

    print(int(ans))

Submission status: Accepted

Solution code:
import math

def factorize(n):
    ret={}
    i = 2
    while n >= i**2:
        cnt = 0
        while n % i == 0:
            n //= i
            cnt += 1
        if cnt != 0:
            ret[i] = cnt
        i += 1
    if n != 1:
        ret[n] = 1
    return ret

def combination(n,r):
    ret = 1
    r = min(r, n-r)
    for i in range(n-r+1, n+1):
        ret *= i
    for i in range(1, r+1):
        ret //= i
    return ret


# mの各素因数を振り分ける
# 各素因数p(^a)について，nつに振り分ける
# n-1+a C n-1 
n,m=map(int, input().split())
f = factorize(m)
ans = 1
for k,v in f.items():
    ans *= combination(n-1+v, v)
    ans %= (int(1e9+7))
print(ans)

Submission status: Accepted

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


def combination(n, r):
    r = min(r, n - r)
    result = 1
    for i in range(n - r + 1, n + 1):
        result *= i
    for i in range(1, r + 1):
        result //= i
    return result


def factorize(x):
    i = 2
    result = {}
    while True:
        if i**2 > x:
            break
        count = 0
        while x % i == 0:
            x //= i
            count += 1
        if count != 0:
            result[i] = count
        i += 1
    if x > 1:
        result[x] = 1
    return result


ans = 1
mod = 10**9 + 7
result = factorize(M)
for e in result.values():
    comb = combination(e + N - 1, e) % mod
    ans = ans * comb % mod

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, os
try: from typing import Any, Union, List, Tuple, Dict
except ImportError: pass
sys.setrecursionlimit(10**6)
if os.environ.get("USER") == "shun":
    def debug(*args): print(*args, file=sys.stderr)
else:
    print("NO DEBUG", file=sys.stderr)
    def debug(*args): pass
def exit(): sys.exit(0)


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

p = 10**9 + 7
# 素因数分解
def prime_factorization(n):
    factors = {}
    q = 2
    while n != 1:
        if q**2 > n:
            factors[n] = 1
            break
        while n % q == 0:
            n = n // q
            if q in factors:
                factors[q] += 1
            else:
                factors[q] = 1
        q += 1
    return factors


def power(n, e):
    # debug(".")
    if e == 0:
        return 1
    if e % 2 == 0:
        return power(n**2%p, e//2) % p
    return n * power(n, e-1) % p


def inv(n):
    return power(n, p-2)


# def comb(a, b):
#     if a < b:
#         a, b = b, a
#     assert a >= b
#     res = 1
#     for i in range(a+1, a+b+1):
#         res = (res * i) % p
#     for i in range(1, b+1):
#         res = (res * inv(i)) % p
#     return res


bunbo = 1
for i in range(1, n):
    # debug(i)
    bunbo = (bunbo * i) % p
debug("foo")
bunbo = inv(bunbo)
debug("hoge")

ans = 1
fact = prime_factorization(m)
for q in fact:
    debug(q)
    k = fact[q]
    cur = 1
    for i in range(k+1, n+k):
        cur = (cur * i) % p
    ans = (ans * cur) % p
ans = (ans * power(bunbo, len(fact))) % p
print(ans)

Submission status: Accepted

Solution code:
def fctr(n):
    f = []
    c = 0
    for i in range(2,int(n**0.5)+1):
        while n%i==0:
            c+=1
            n = n//i
        if c!=0:
            f.append([i,c])
            c = 0

    if n!=1:
        f.append([n,1])

    return f

def combination(n,r):
    r = min(r,n-r)
    result = 1
    for i in range(n-r+1,n+1):
        result *= i
    for i in range(1,r+1):
        result //= i
    return result

mod = 10**9 + 7
N,M = list(map(int,input().split()))
ans = 0
s = fctr(M)

for i in s:
    if ans == 0:
        ans = combination(N-1+i[1],i[1]) % mod
    else:
        ans = (ans*combination(N-1+i[1],i[1]))%mod

if M != 1:         
    print(ans)
else:
    print('1')

Submission status: Accepted

Solution code:
import math
import random
class Prime:
    seed_primes=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
    def is_prime(self,n):
        is_prime_common=self.is_prime_common(n)
        if is_prime_common is not None:return is_prime_common
        if n<2000000:return self.is_prime_brute_force(n)
        return self.is_prime_miller_rabin(n)
    def is_prime_common(self,n):
        if n==1:return False
        if n in Prime.seed_primes:return True
        if any(map(lambda x:n%x==0,self.seed_primes)):return False
    def is_prime_brute_force(self,n):
        for k in range(2,int(math.sqrt(n))+1):
            if n%k==0:return False
        return True
    def is_prime_miller_rabin(self,n):
        d=n-1
        while d&1==0:d>>=1
        witnesses=self.get_witnesses(n)
        for w in witnesses:
            y=pow(w,d,n)
            while d!=n-1and y!=1and y!=n-1:
                y=y*y%n
                d<<=1
            if y!=n-1and d&1==0:return False
        return True
    def get_witnesses(self,num):
        def _get_range(num):
            if num<2047:return 1
            if num<1373653:return 2
            if num<25326001:return 3
            if num<3215031751:return 4
            if num<2152302898747:return 5
            if num<3474749660383:return 6
            if num<341550071728321:return 7
            if num<3825123056546413051:return 9
            return 12
        return self.seed_primes[:_get_range(num)]
    def gcd(self,a,b):
        if a<b:return self.gcd(b,a)
        if b==0:return a
        while b:a,b=b,a%b
        return a
    @staticmethod
    def f(x,n,seed):
        p=Prime.seed_primes[seed%len(Prime.seed_primes)]
        return(p*x+seed)%n
    def find_factor(self,n,seed=1):
        if self.is_prime(n):return n
        x,y,d=2,2,1
        count=0
        while d==1:
            count+=1
            x=self.f(x,n,seed)
            y=self.f(self.f(y,n,seed),n,seed)
            d=self.gcd(abs(x-y),n)
        if d==n:
            return self.find_factor(n,seed+1)
        return self.find_factor(d)
    # nのすべての素因数を見つける
    def find_factors(self,n):
        primes={}
        if self.is_prime(n):
            primes[n]=1
            return primes
        while n>1:
            factor=self.find_factor(n)
            primes.setdefault(factor,0)
            primes[factor]+=1
            n//=factor
        return primes
class Factorial:
    def __init__(self,n,mod):
        self.f=[1]
        for i in range(1,n+1):
            self.f.append(self.f[-1]*i%mod)
        self.i=[pow(self.f[-1],mod-2,mod)]
        for i in range(1,n+1)[::-1]:
            self.i.append(self.i[-1]*i%mod)
        self.i.reverse()
    def factorial(self,i):
        return self.f[i]
    def ifactorial(self,i):
        return self.i[i]
    def comb(self,n,k):
        return self.f[n]*self.i[n-k]%mod*self.i[k]%mod
mod=10**9+7
n,m=map(int,input().split())
*d,=Prime().find_factors(m).values()
if d:f=Factorial(n+max(d),mod)
ans=1
for t in d:
    ans=ans*f.comb(n-1+t,t)%mod
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import math

class Prime:
    seed_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

    def is_prime(self, n):
        is_prime_common = self.is_prime_common(n)
        if is_prime_common is not None:
            return is_prime_common

        if n < 2000000:
            return self.is_prime_bf(n)
        else:
            return self.is_prime_mr(n)

    def is_prime_common(self, n):
        if n == 1: return False
        if n in Prime.seed_primes: return True
        if any(map(lambda x: n % x == 0, self.seed_primes)): return False

    def is_prime_bf(self, n):
        for k in range(2, int(math.sqrt(n)) + 1):
            if n % k == 0:
                return False
        return True

    def is_prime_mr(self, n):
        d = n - 1
        while d % 2 == 0:
            d //= 2

        witnesses = self.get_witnesses(n)

        for w in witnesses:
            y = pow(w, d, n)

            while d != n - 1 and y != 1 and y != n - 1:
                y = (y ** 2) % n
                d *= 2

            if y != n - 1 and d % 2 == 0:
                return False

        return True

    def get_witnesses(self, num):
        def _get_range(num):
            if num < 2047:
                return 1
            if num < 1373653:
                return 2
            if num < 25326001:
                return 3
            if num < 3215031751:
                return 4
            if num < 2152302898747:
                return 5
            if num < 3474749660383:
                return 6
            if num < 341550071728321:
                return 7
            if num < 38255123056546413051:
                return 9
            return 12

        return self.seed_primes[:_get_range(num)]

    def gcd(self, a, b):
        if a < b:
            a, b = b, a
        if b == 0:
            return a
        while b:
            a, b = b, a % b
        return a

    @staticmethod
    def f(x, n, seed):
        p = Prime.seed_primes[seed % len(Prime.seed_primes)]
        return (p * x + seed) % n

    def find_factor(self, n, seed=1):
        if self.is_prime(n):
            return n

        x, y, d = 2, 2, 1
        count = 0
        while d == 1:
            count += 1
            x = self.f(x, n, seed)
            y = self.f(self.f(y, n, seed), n, seed)
            d = self.gcd(abs(x - y), n)

        if d == n:
            return self.find_factor(n, seed+1)
        return self.find_factor(d)

    def find_factors(self, n):
        primes = {}
        if self.is_prime(n):
            primes[n] = 1
            return primes

        while n > 1:
            factor = self.find_factor(n)

            primes.setdefault(factor, 0)
            primes[factor] += 1

            n //= factor

        return primes

prime = Prime()

def main():
    [N, M] = list(map(int, input().split()))

    prime = Prime()

    factors = prime.find_factors(M)
    d = 10 ** 9 + 7

    r = 1
    for v in factors.values():
        if v == 1:
            r *= N
            r %= d
        else:
            lst = [i for i in range(2, v + 1)]
            for i in range(1, v + 1):
                r *= N + v - i
                for j in range(len(lst)):
                    if r % lst[j] == 0:
                        r //= lst[j]
                        lst.pop(j)
                        break
            for j in range(len(lst)):
                r //= lst[j]
            r %= d

    print(r)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
MOD = 1000000007
def comb(x, y):
    ret = 1
    for a in range(x, x - y, -1):
        ret = ret * a % MOD
    ret = ret * inverse(fact(y)) % MOD
    return ret

def fact(x):
    if x == 0:
        return 1
    return x * fact(x - 1) % MOD


def inverse(x):
    return pow(x, MOD - 2, MOD)
ans = 1
for i in range(2, 100000):
    if i > m:break
    cnt = 0
    while m % i == 0:
        cnt += 1
        m //= i
    ans = ans * comb(cnt + n - 1, cnt) % MOD
if m != 1:
    ans = ans * comb(n, 1) % MOD

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
MOD = 1000000007
def comb(x, y):
    ret = 1
    for a in range(x, x - y, -1):
        ret *= a
    for b in range(y, 0, -1):
        ret //= b
    return ret

ans = 1
for i in range(2, 100000):
    if i > m:break
    cnt = 0
    while m % i == 0:
        cnt += 1
        m //= i
    ans *= comb(cnt + n - 1, cnt)
if m != 1:
    ans *= comb(n, 1)

print(ans % MOD)

Submission status: Accepted

Solution code:
from collections import Counter
from scipy.misc import comb
c=Counter()
n,m=map(int,input().split())
t=2
while(t**2 <= m):
    if m%t:
        t+=1
        continue
    while m%t==0:
        c[t]+=1
        m//=t
if m>1:c[m]+=1
a=1
for i in c:
    a=a*comb(n+c[i]-1,n-1,exact=1)%(10**9+7)
print(a)

Submission status: Accepted

Solution code:
import math
import random
from scipy.misc import comb
class Prime:
    seed_primes=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
    def is_prime(self,n):
        is_prime_common=self.is_prime_common(n)
        if is_prime_common is not None:return is_prime_common
        if n<2000000:return self.is_prime_brute_force(n)
        return self.is_prime_miller_rabin(n)
    def is_prime_common(self,n):
        if n==1:return False
        if n in Prime.seed_primes:return True
        if any(map(lambda x:n%x==0,self.seed_primes)):return False
    def is_prime_brute_force(self,n):
        for k in range(2,int(math.sqrt(n))+1):
            if n%k==0:return False
        return True
    def is_prime_miller_rabin(self,n):
        d=n-1
        while d&1==0:d>>=1
        witnesses=self.get_witnesses(n)
        for w in witnesses:
            y=pow(w,d,n)
            while d!=n-1and y!=1and y!=n-1:
                y=y*y%n
                d<<=1
            if y!=n-1and d&1==0:return False
        return True
    def get_witnesses(self,num):
        def _get_range(num):
            if num<2047:return 1
            if num<1373653:return 2
            if num<25326001:return 3
            if num<3215031751:return 4
            if num<2152302898747:return 5
            if num<3474749660383:return 6
            if num<341550071728321:return 7
            if num<3825123056546413051:return 9
            return 12
        return self.seed_primes[:_get_range(num)]
    def gcd(self,a,b):
        if a<b:return self.gcd(b,a)
        if b==0:return a
        while b:a,b=b,a%b
        return a
    @staticmethod
    def f(x,n,seed):
        p=Prime.seed_primes[seed%len(Prime.seed_primes)]
        return(p*x+seed)%n
    def find_factor(self,n,seed=1):
        if self.is_prime(n):return n
        x,y,d=2,2,1
        count=0
        while d==1:
            count+=1
            x=self.f(x,n,seed)
            y=self.f(self.f(y,n,seed),n,seed)
            d=self.gcd(abs(x-y),n)
        if d==n:
            return self.find_factor(n,seed+1)
        return self.find_factor(d)
    def find_factors(self,n):
        primes={}
        if self.is_prime(n):
            primes[n]=1
            return primes
        while n>1:
            factor=self.find_factor(n)
            primes.setdefault(factor,0)
            primes[factor]+=1
            n//=factor
        return primes
n,m=map(int,input().split())
a=1
for c in Prime().find_factors(m).values():
    a=a*comb(n+c-1,c,exact=1)%(10**9+7)
print(a)

Submission status: Accepted

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

mod = 10 ** 9 + 7


'''Snippets for combination.

Available functions:
- count_combination: Count the total number of combinations.
'''


def count_combination(n: int, r: int, mod: int = 10 ** 9 + 7) -> int:
    '''Count the total number of combinations.
        nCr % mod.

    Args:
        n   : Elements. Int of number (greater than 1).
        r   : The number of r-th combinations. Int of number (greater than 0).
        mod : Modulo. The default is 10 ** 9 + 7.

    Returns:
        The total number of combinations.

    Landau notation: O(n)

    See:
    https://qiita.com/derodero24/items/91b6468e66923a87f39f
    '''

    if r > (n - r):
        return count_combination(n, n - r)

    if r == 0 or r == n:
        return 1

    if r == 1:
        return n

    multiple = 1
    division = 1

    for i in range(r):
        multiple *= n - i
        division *= i + 1
        multiple %= mod
        division %= mod

    return multiple * pow(division, mod - 2, mod) % mod


def solve(n: int, m: int):
    from math import sqrt

    ans = 1
    remain = m

    for j in range(2, int(sqrt(m)) + 1):
        if remain % j == 0:
            count = 0

            while remain % j == 0:
                count += 1
                remain //= j

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

    if remain != 1:
        ans *= count_combination(n, 1)
        ans %= mod

    return ans


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

    # See:
    # https://www.youtube.com/watch?v=gdQxKESnXKs
    print(solve(n, m))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

while(m**2 <= M):
    if M%m == 0:
        while(M%m == 0):
            c[m] += 1
            M //= m
    else:
        m += 1
if M > 1 : c[M] += 1
MAXN = N+100
fac = [0 for _ in range(MAXN)]
inv = [0 for _ in range(MAXN)]
finv = [0 for _ in range(MAXN)]
fac[0] = fac[1] = 1
inv[1] = 1
finv[0] = finv[1] = 1
for i in range(2,MAXN):
    fac[i] = (i*fac[i-1]) % MOD
    inv[i] = (-inv[MOD%i]*(MOD//i))%MOD
    finv[i] = (finv[i-1]*inv[i])%MOD

def comb(n,k):
    return (fac[n]*(finv[k]*finv[n-k]%MOD))%MOD
ans = 1
for i in c:
    ans *= comb(c[i]+N-1,N-1)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
import math
n,m =map(int,input().split())
 
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(int(n))
  return table
 
a =prime_decomposition(m)

def combination(n,r):
    r = min(r,n-r)
    result = 1
    for i in range(n-r+1,n+1):
        result *= i
    for i in range(1,r+1):
        result //= i
    return result

ans=1
count = 1
if not a:
  print(ans)
  exit()

for i in range(1,len(a)):
  if a[i-1]== a[i]:
    count +=1
  else:
    ans *= combination(count+n-1,count)
    ans %=1000000007
    count = 1
    
ans *= combination(count+n-1,count)
ans %=1000000007
print(ans)

Submission status: Accepted

Solution code:
# 素因数分解 ソート済みリスト (素因数,指数)
import math
def factoring(n,dict_count = {}):
    sup = math.floor(pow(n,1/2))
    n_new = n
    for i in range(2,sup + 1):
        if n % i == 0:
            n_new = n // i
            if i in dict_count:
                dict_count[i] += 1
            else:
                dict_count[i] = 1
            break
    if n == n_new:
        if n_new in dict_count:
            dict_count[n_new] += 1
        else:
            dict_count[n_new] = 1
        return sorted(list(dict_count.items()))
    return factoring(n_new,dict_count)

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

N,M = map(int,input().split())
if M == 1:
    print(1)
    exit()
ans = 1
for a,b in factoring(M):
    ans *= comb(b+N-1,b)
    ans %= 10**9 + 7
print(ans)

Submission status: Accepted

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

factor = []
tmp = M
i = 2
while i**2 <= M:
    while tmp % i == 0:
        factor.append(i)
        tmp //= i
    i += 1
if tmp != 1:
    factor.append(tmp)

arr = Counter(factor).values()


dp = [-1 for _ in range(200001)]


def factorize(n):
    if dp[n] != -1:
        return dp[n]
    if n == 1:
        return 1
    return n*factorize(n-1)


def combination(n, k):
    i = n
    res = 1
    while i > n-k:
        res *= i
        i -= 1
    return res//factorize(k)

ans = 1
for elem in arr:
    ans *= combination(elem+N-1, elem)
    ans %= mod

print(ans)

Submission status: Accepted

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

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

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

ans = 1
for v in nprf(m).values():
    ans = ans * comb(v+n-1, v) % mod
    
print(ans)

Submission status: Accepted

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

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

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

ans = 1
for v in prf(m).values():
    ans = ans * comb(n-1+v, v) % mod
    
print(ans)

Submission status: Accepted

Solution code:
import math
mod = 10 ** 9 + 7
n, m = map(int, input().split())

f = []
p = 2
while p * p <= m:
    if m % p != 0:
        p += 1
        continue
    c = 0
    while m % p == 0:
        c += 1
        m //= p
    f.append(c)
    p += 1
if m != 1:
    f.append(1)


def comb(a, b):
    ret = 1
    r = min(b, a-b)
    for i in range(a-r+1, a+1):
        ret *= i
    for j in range(1, r+1):
        ret //= j

    return (int)(ret)


ans = 1
for i in f:
    ans *= comb(i+n-1, i)
print(ans % mod)

Submission status: Accepted

Solution code:
#素因数分解
def prf(m):
    pf = {}
    for i in range(2, int(m**0.5)+1):
        while m % i == 0:
            pf[i] = pf.get(i, 0)+1
            #get:辞書のkeyを指定し、そのkeyがあればvalueを返し、なければ指定した値を返す
            m //= i
    if m > 1:
        pf[m] = 1
        #mの平方根よりも大きい数が残る場合はその数自体が素因数(m=10=2*5)
    return pf

#組合せ（nCk）
def comb(n, k):
    k = min(k, n - k)
    result = 1
    for i in range(n, n - k, -1):
        result *= i
    for i in range(1, k + 1):
        result //= i 
    return result
 
n, m = map(int, input().split())
mod = 10 ** 9 + 7

ans = 1
for i in prf(m).values():
    ans = ans * comb(n - 1 + i, i) % mod
    #重複組合せ：N-1枚の仕切り（aとaの間の個数に相当）を使って、i（指数）を振り分ける場合の数
print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

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

f = []
p = 2
while p * p <= M:
    if M % p != 0:
        p += 1
        continue
    c = 0
    while M % p == 0:
        c += 1
        M //= p
    f.append(c)
    p += 1
if M != 1:
    f.append(1)

ans = 1
for i in f:
    c = 1
    for j in range(i):
        c = c * (N + j) // (j + 1)
    ans = ans * c % MOD
print(ans)

Submission status: Accepted

Solution code:
from math import factorial

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

pdic={}

p=2
while M>1:
    c=0
    while M%p==0:
        c+=1
        M//=p
    if c>0:
        pdic[p]=c
    p+=1

ans=1
tmp=factorial(N-1)

for p in pdic.keys():
    e=pdic[p]
    ans*=factorial(N+e-1)//(factorial(e)*tmp)

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

Submission status: Accepted

Solution code:
from math import factorial

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

pdic={}

p=2
while p**2<=M:
    c=0
    while M%p==0:
        c+=1
        M//=p
    if c>0:
        pdic[p]=c
    p+=1
if M>1:
    pdic[M]=1

ans=1
tmp=factorial(N-1)

for p in pdic.keys():
    e=pdic[p]
    ans*=factorial(N+e-1)//(factorial(e)*tmp)

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

Submission status: Accepted

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

# 重複組み合わせ
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


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


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

print(ans)

Submission status: Accepted

Solution code:
import math

def prime_factorize(n):
    ret = []
    # 小さい素数から順に試し割りしていく
    for i in range(2, int(math.sqrt(n))+1):
        if n % i != 0:
            continue
        e = 0
        while n % i == 0:
            e += 1
            n //= i
        ret += [(i, e)]

    if n != 1:
        ret += [(n, 1)]

    return ret


def extgcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
        g = b
    return x, y, g


def modinv(a, m):
    x, y, g = extgcd(a, m)
    if g != 1:
        print ("[+]Inverse does not exist.")
    else:
        return ((m + x) % m) % m


def mod_comb(n, r, mod):
    ans_mul, ans_div = 1, 1

    for i in range(r):
        ans_mul *= (n-i)
        ans_div *= (i+1)
        ans_mul %= mod
        ans_div %= mod

    return ans_mul * modinv(ans_div, mod) % mod


def main():
    N, M = map(int, input().split())
    v = prime_factorize(M)
    MOD = int(10**9+7)
    ans = 1

    for i in v:
        ans *= mod_comb(N+i[1]-1, i[1], MOD)
        ans %= MOD
    print (ans)

main()

Submission status: Accepted

Solution code:
import math

def prime_factorize(n):
    ret = []
    # 小さい素数から順に試し割りしていく
    for i in range(2, int(math.sqrt(n))+1):
        if n % i != 0:
            continue
        e = 0
        while n % i == 0:
            e += 1
            n //= i
        ret += [(i, e)]

    if n != 1:
        ret += [(n, 1)]

    return ret


def extgcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
        g = b
    return x, y, g


def modinv(a, m):
    x, y, g = extgcd(a, m)
    if g != 1:
        print ("[+]Inverse does not exist.")
    else:
        return ((m + x) % m) % m


def calc_comb(n, r, mod):
    ans_mul, ans_div = 1, 1

    for i in range(r):
        ans_mul *= (n-i)
        ans_div *= (i+1)
        ans_mul %= mod
        ans_div %= mod

    return ans_mul * modinv(ans_div, mod) % mod


def main():
    N, M = map(int, input().split())
    v = prime_factorize(M)
    MOD = int(10**9+7)
    ans = 1

    for i in v:
        ans *= calc_comb(N+i[1]-1, i[1], MOD)
        ans %= MOD
    print (ans)

main()