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:
n,M=map(int,input().split())
from math import factorial
i=2
c_list=[]
m=M
while i**2<=M:
    count=0
    while m%i==0:
        m=m//i
        count=count+1
    if not count==0:
        c_list.append(count)
    i=i+1
if not m==1:
    c_list.append(1)
if M==1:
    print(1)
else:
    INF=10**9+7
    Sum=1
    for i in c_list:
        Sum=Sum*(factorial(n-1+i)//(factorial(n-1)*factorial(i)))
        Sum=Sum%INF
    print(Sum)

Submission status: Accepted

Solution code:
n,M=map(int,input().split())
from math import factorial
i=2
c_list=[]
m=M
while not m==1:
    count=0
    while m%i==0:
        m=m//i
        count=count+1
    if not count==0:
        c_list.append(count)
    i=i+1
if M==1:
    print(1)
else:
    INF=10**9+7
    Sum=1
    for i in c_list:
        Sum=Sum*(factorial(n-1+i)//(factorial(n-1)*factorial(i)))
        Sum=Sum%INF
    print(Sum)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n,h,w = LI()
    x = LI()
    t = [0 for i in range(w*n+1)]
    for i in range(n):
        if not i%2:
            t[i*w+x[i]] += 1
            t[(i+1)*w+x[i]] -= 1
        else:
            t[i*w-x[i]] += 1
            t[(i+1)*w-x[i]] -= 1
    for i in range(w*n):
        t[i+1] += t[i]
    ans = 0
    for i in t[:-1]:
        if i == 0:
            ans += h
    print(ans)
    return

#B
def B():
    def dfs(d,x):
        for i in range(d):
            print(".",end = "")
        print(lis[x])
        for y in v[x]:
            dfs(d+1,y)

    n = I()
    v = [[] for i in range(n)]
    lis = [None for i in range(n)]
    for i in range(n):
        k = I()
        lis[i] = input()
        if k > 0:
            v[k-1].append(i)
    dfs(0,0)
    return

#C
def C():
    def dfs(d,k):
        if d == n:
            l.append(k)
        else:
            if sum(k[-2:]) == 0 and len(k) > 1:
                dfs(d+1,k+[1])
            elif d == n-1:
                dfs(d+1,k+[1])
            else:
                dfs(d+1,k+[0])
                dfs(d+1,k+[1])
    n = I()
    l = []
    dfs(0,[])
    print(len(l))
    return

#D
def D():
    def factorize(n):
        if n < 4:
            return {n:1}
        lis = {}
        i = 2
        m = n
        while i**2 <= m:
            if m%i == 0:
                lis[i] = 0
                while m%i == 0:
                    m //= i
                    lis[i] += 1
            i += 1
        if m != 1:
            lis[m] = 1
        return lis
    n,m = LI()
    if m == 1:
        print(1)
        quit()
    l = factorize(m)
    fact = [None for i in range(200001)]
    fact[0] = 1
    for i in range(200000):
        fact[i+1] = fact[i]*(i+1)
        if fact[i+1] >= mod:
            fact[i+1] %= mod
    inv = [None for i in range(200001)]
    inv[200000] = pow(fact[200000],mod-2,mod)
    for i in range(200000)[::-1]:
        inv[i] = inv[i+1]*(i+1)
        if inv[i] >= mod:
            inv[i] %= mod
    ans = 1
    for i in l.values():
        ans *= (fact[n+i-1]*inv[i]*inv[n-1])%mod
        if ans >= mod:
            ans %= mod
    print(ans)
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#I
def I_():
    return

#J
def J():
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

import math
from operator import mul
from functools import reduce


inf = 10**9+7


# nCr
def combination(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under


# nまでの素数を列挙する
class PrimeUtil:
    def __init__(self, n):
        self.l_is_prime = [True for _ in range(n+1)]
        self.l_is_prime[0] = False
        self.l_is_prime[1] = False
        self.n = n
        self.primes = []
        for k in range(2, n+1):
            if self.l_is_prime[k]:
                self.primes.append(k)
                self._set_false(k)

    # pの倍数全てのl_is_primeのフラグをFalseにする
    def _set_false(self, p):
        k = p
        for _ in range(1, self.n//p):
            k += p
            self.l_is_prime[k] = False

    # 素因数分解した結果を返す
    def factor(self, k):
        ret = {}
        tmp = k
        for p in self.primes:
            if p > tmp:
                break
            while True:
                if tmp % p != 0:
                    break
                ret.setdefault(p, 0)
                ret[p] += 1
                tmp /= p
                if tmp == 1:
                    break
        if tmp > 1:
            ret[tmp] = 1
        return ret


def main():
    N, M = list(map(int, input().split()))
    pu = PrimeUtil(100000)
    ans = 1
    f = pu.factor(M)
    for v in f.values():
        ans *= combination(v+N-1, v)
        ans %= inf
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

import math
sM = int(math.sqrt(M)+1)

p_li = []
m = M
for j in range(2,sM+1):
  for i in range(sM):
    if (m%j)==0:
      p_li.append(j)
      m//=j
    else:
      break
  if (m==1):
    break
if (m!=1):
  p_li.append(m)
    
    
import collections
co = collections.Counter(p_li)
vec = co.values()

def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

s = 1
for v in vec:
  X=N-1+v
  Y=N-1
  if (X-Y<Y):
    Y=X-Y
  ss = 1
  sd = 1
  for i in range(X,X-Y,-1):
    ss = (ss*i)%MOD
  for i in range(Y,0,-1):
    sd = (sd*i)%MOD
  
  ss = (ss*mod_inv(sd,MOD))%MOD
  s = (s*ss)%MOD
print (s%MOD)

Submission status: Accepted

Solution code:
from itertools import combinations
from collections import Counter
import operator as op
from functools import reduce

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 = [int(i) for i in input().split()]

def primes(n):
    primfac = []
    d = 2
    while d*d <= n:
        while (n % d) == 0:
            primfac.append(d)  # supposing you want multiple factors repeated
            n //= d
        d += 1
    if n > 1:
        primfac.append(n)
    return primfac

ans = 1
divisors = primes(M)
for k, v in Counter(divisors).items():
    ans *= ncr(N - 1 + v, v)
print(ans % (10**9 + 7))

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

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

n,m = li()

MOD = 10**9 + 7

from collections import Counter

def factorize(n: int):
    d = Counter()
    m = 2

    while m * m <= n:
        while n % m == 0:
            n //= m
            d[m] += 1

        m += 1

    if n > 1:
        d[n] += 1

    return d

# 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


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

divs = factorize(m)
ans = 1

for _, vals in divs.items():
    ans *= nCr(vals+n-1, vals, MOD, fac, fac_inv)
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
def FACTOR(DICT, N):
    FACT = DICT
    LIM = int(N**0.5)+2
    for i in range(2, LIM):
        if N%i == 0:
            FACT[i] = 0
        while N%i == 0:
            FACT[i] += 1
            N //= i
    if len(FACT) == len(DICT):
        if N != 1:
            FACT[N] = 1
        return FACT
    return FACTOR(FACT, N)

def comb_rep(n, r):
    N = n+r-1
    ANS = 1
    for R in range(r):
        ANS *= N-R
    for R in range(r):
        ANS //= r-R
    return int(ANS)

MOD = 10**9+7
n, m = map(int, input().split())
factor = FACTOR({}, m)
ans = 1
for i in factor:
    ans *= (comb_rep(n, factor[i])%MOD)
    ans %= MOD
print(ans)

Submission status: Accepted

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

# 素因数分解(小さい方から順に割っていく。sqrt(2)まで)
def factorize(n):
    i = 2
    table = [0]
    cnt= [0]
    while i * i <= n:
        while n % i == 0:
            n /= i
            if table[-1] != i:
                table.append(i)
                cnt.append(0)
            cnt[-1] += 1
        i += 1
    if n > 1:
        table.append(n)
        cnt.append(1)
    return table,cnt


fs,ns = factorize(M)
ans = 1
for n in ns[1:]:
    a = 1
    for i in range(N,n+N):
        a *= i
    ans *= a//factorial(n)
print(ans%(10**9+7))

Submission status: Accepted

Solution code:
from math import factorial

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

if M==1:
  print(1)
  exit()
MOD=(10**9)+7
def trial_division(n):
    #素因数を格納するリスト
    factor = []
    #2から√n以下の数字で割っていく
    tmp = int(n**0.5) + 2
    for num in range(2,tmp):
        count=0
        while n % num == 0:
            n //= num
            count+=1
        if count>0:
          factor.append(count)
    #リストが空ならそれは素数
    if not factor:
        return [1]
    elif n!=1:
        factor.append(1)
        return factor
    else:
        return factor


factor=trial_division(M)

ans=1
for a in factor:
  for i in range(a):
    ans*=N+i
  ans //= factorial(a)
  ans%=MOD

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
from math import*
from collections import deque
from collections import defaultdict
from itertools import permutations
from heapq import*
from collections import Counter
from itertools import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = 10**18
from functools import reduce


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

d = factorial(n-1)
ans = 1
for p in pdic.keys():
    num = pdic[p]
    ans *= factorial(num+n-1)//(factorial(num)*d)
print(ans%(10**9+7))

Submission status: Accepted

Solution code:
###############################################################################

from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


###############################################################################


mod = 10**9 + 7


def combination(x, y):
    assert(x >= y)

    if y > x // 2:
        y = x - y

    ret = 1

    for i in range(0, y):
        j = x - i
        i = i + 1

        ret = ret * j
        ret = ret // i

    return ret


def calc_orderd_dp(divided, max_count):
    if max_count <= 1:
        return 1
    if divided == 1:
        return max_count
    if divided <= 0:
        return 1

    ret = 0
    for i in range(min(divided, max_count)):
        i += 1
        comb = combination(max_count, i)
        dp = calc_orderd_dp(divided - i, i)
        ret = modadd(ret, comb * dp)

    return ret


def main():
    n, m = intin()

    factors = get_factors(m)

    factors_count = {}
    for factor in factors:
        if factor <= 1:
            continue
        factors_count.setdefault(factor, 0)
        factors_count[factor] += 1

    ans = 1

    for factor, count in factors_count.items():
        ans = modmlt(ans, calc_orderd_dp(count, n))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

if N==1:
    print(1)
    exit()
else:
        
    
    L=[0 for i in range((10**5)+1)]
    for i in range(2,10**5):
        while M%i==0:
            L[i]+=1
            M//=i
        if M==1:
            break
    if M>1:
        L.append(1)
    
    mod=(10**9+7)
    
    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 #出力の制限
    N1 = (10**5)*2
    g1 = [1, 1] # 元テーブル
    g2 = [1, 1] #逆元テーブル
    inverse = [0, 1] #逆元テーブル計算用テーブル
    
    for i in range( 2, N1 + 1 ):
        g1.append( ( g1[-1] * i ) % mod )
        inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
        g2.append( (g2[-1] * inverse[-1]) % mod )
    ans=1
    for i in range(len(L)):
        if L[i]!=0:
            ans*=cmb(L[i]+N-1,min(L[i],N),mod)
            ans%=mod
            
    print(ans)

Submission status: Accepted

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

factor = []
tmp = int(m ** (1/2)) + 1
for i in range(2, tmp):
    while m % i == 0:
        m //= i
        factor.append(i)
if m > 1:
    factor.append(m)
num = list(collections.Counter(factor).most_common())

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

ans = 1
for x in num:
    ans *= (comb(x[1] + n - 1, x[1]) % 1000000007)
    ans %= 1000000007
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int, input().split())
def is_prime(N):
    is_prime=[True]*(N+1)
    is_prime[0:2]=False,False
    for i in range(int(N**0.5)+1):
        if is_prime[i]==False:
            continue
        for j in range(i*2,N+1,i):
            is_prime[j]=False
    return is_prime
def primes(N):
    prime=is_prime(N)
    return [i for i in range(N+1) if prime[i]]
def prime_factorization(n):
    ps=primes(int(n**0.5))
    r=[]
    for i,p in enumerate(ps):
        num=0
        while(True):
            x,y=divmod(n,p)
            if y!=0:
                break
            n=x
            num+=1
        if num>0:
            r.append((p,num))
    if n>1:
        r.append((n,1))
    return r
mod=10**9+7
def add(a,b):
    return (a+b)%mod
def sub(a,b):
    return (a-b)%mod
def mul(a,b):
    return ((a%mod)*(b%mod))%mod
def pow(x,y):
    if y==0:
        return 1
    elif y==1:
        return x%mod
    elif y%2==0:
        return pow(x,y//2)**2 % mod
    else:
        return pow(x,y//2)**2 * x % mod
def div(a,b):
    return mul(a,pow(b,mod-2))
def fac(n):
    a=1
    for i in range(2,n+1):
        a=mul(a,i)
    return a

f=prime_factorization(m)
ans=1
for p in f:
    ans=mul(ans,fac(p[1]+n-1))
    ans=div(ans,fac(p[1]))
    ans=div(ans,fac(n-1))
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
MOD = 10 ** 9 + 7
import sys
frac_list = [0 for i in range(100)]

def comb_cal(n,r):
    tmp = 1
    for i in range(r):
        tmp *= (n - i)
    for i in range(r):
        tmp //= r - i
    return tmp

frac = []
while True:
    for i in range(2,int(M**(1/2))+1):
        if M % i == 0:
            frac.append(i)
            M //= i
            break
    else:
        break
if M > 1:
    frac.append(M)
def counter(array):
    from collections import Counter
    return list(Counter(array).most_common())
c = counter(frac)
ans = 1
for x in c:
    ans *= (comb_cal(x[1]+N-1,x[1]) % MOD)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
import math

def getPrimeFactorsDict(num):
  pn = 2 #素数は2から
  pfdict = {} #素因数のリスト
  while pn * pn <= num: #√numまで調べる
    while num % pn == 0: #現在の素数で割り切れる範囲でループ
      num = num / pn
      pfdict[pn] = pfdict.get(pn, 0) + 1
    pn += 1 #割り切れなくなったら次の素数へ
  if num > 1:
    pfdict[int(num)] = pfdict.get(int(num), 0) + 1
    
  return pfdict


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

d = getPrimeFactorsDict(M)

ans = 1
for key in d.keys():

  if d[key] == 1:
    ans *= N
  else:
    ans *= math.factorial(N+d[key]-1) // (math.factorial(N-1) *  math.factorial(d[key]))

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

Submission status: Accepted

Solution code:
def soin(num):
    re = []
    div = 2
    while 1:
        lim = int(num ** 0.5) + 1
        while num % div:
            div += 1
            if div > lim:
                re += [1]
                return re
        sisu = 0
        while num % div == 0:
            num //= div
            sisu += 1
        re += [sisu]
        if num == 1:
            return re


def com(a, b):
    if a == b:
        return 1
    t = (a, b)
    if (a, b) in com_memo:
        return com_memo[t]
    re = com(a - 1, b) * a // (a - b)
    com_memo[t] = re
    return re


def f(n, m):
    if m == 1:
        print(1)
        return
    sisus = soin(m)
    ans = 1
    for s in sisus:
        ans = ans * com(s + n - 1, n - 1) % md
    print(ans)


md = 10 ** 9 + 7
n, m = map(int, input().split())
com_memo = {}
f(n, m)

Submission status: Accepted

Solution code:
def soin(num):
    re = []
    div = 2
    while 1:
        lim = int(num ** 0.5) + 1
        while num % div:
            div += 1
            if div > lim:
                re += [1]
                return re
        sisu = 0
        while num % div == 0:
            num //= div
            sisu += 1
        re += [sisu]
        if num == 1:
            return re


def com(a, b):
    if a == b:
        return 1
    t = (a, b)
    if (a, b) in com_memo:
        return com_memo[t]
    re = com(a - 1, b) * a // (a - b)
    com_memo[t] = re
    return re


def f(n, m):
    sisus = soin(m)
    ans = 1
    for s in sisus:
        ans = ans * com(s + n - 1, n - 1) % md
    print(ans)


md = 10 ** 9 + 7
n, m = map(int, input().split())
if m==1:
    print(1)
    exit()
com_memo = {}
f(n, m)

Submission status: Accepted

Solution code:
N,M = 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 modpow(a,n,mod):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res

def modinv(a,mod):
    return modpow(a,mod - 2,mod)

def cnk(a,b):
    MOD = 10**9+7
    ret = 1
    for i in range(b):
        ret *= (a-i)
        ret %= MOD
        ret = ret * modinv(i+1,MOD) % MOD
    return ret

lis = factorize(M)
ans = 1
for l in lis:
    ans *= cnk(l[1]+N-1,N-1)
    ans %= 10**9+7

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import collections
from operator import mul
from functools import reduce
N, M = map(int, input().split())

def cmb(n, r):
    r = min(r, n-r)
    if r==0: return 1
    over = reduce(mul, range(n, n-r, -1))
    under = reduce(mul, range(1, r+1))
    return over // under

ps = []
tmp = M
for m in range(2, M+1):
    while tmp % m == 0:
        tmp /= m
        ps.append(m)
    if int(tmp) == 1:
        break
    if m*m > M:
        if N > 1:
            ps.append(M)
        break

ps = collections.Counter(ps)

ans = 1
mod = 10**9+7
for c in ps.values():
    ans *= cmb(c+N-1, c) % mod
    if ans > mod:
        ans %= mod

print(ans)

Submission status: Accepted

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

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

def cmb(n,r):
    from operator import mul
    from functools import reduce
    r = min(n - r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

mod = 10 ** 9 + 7
A = prime_decomposition(M)
result = 1
for _, a in A:
    result = result * cmb(a + N - 1, a) % mod

print(result)

Submission status: Accepted

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

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

def cmb(n, r):
    N, R = n, r
    for i in range(1, r):
        N *= n - i
        R *= r - i
    return N // R

mod = 10 ** 9 + 7
A = prime_decomposition(M)
result = 1
for _, a in A:
    result = result * cmb(a + N - 1, a) % mod

print(result)

Submission status: Accepted

Solution code:
N, M = [int(i) for i in 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(n)
  return table

def cmb(n, r):
    N, R = n, r
    for i in range(1, r):
        N *= n - i
        R *= r - i
    return N // R

from collections import Counter
A = Counter(prime_decomposition(M))

mod = 10 ** 9 + 7
result = 1
for a in A.values():
    result = result * cmb(a + N - 1, a) % mod

print(result)

Submission status: Accepted

Solution code:
from functools import reduce
n,m=map(int,input().split())
dic=dict()
p=2
while m>=p*p:
    if m%p==0:
        dic[p]=0
        while m%p==0:
            dic[p]+=1
            m//=p
    p+=1
if m!=1:
    if m not in dic.keys():
        dic[m]=0
    dic[m]+=1
def comb(a,b):
    p=1
    for i in range(a,a-b,-1):
        p*=i
    for i in range(2,b+1):
        p//=i
    return p
l=[comb(i+n-1,i) if 1 not in dic.keys() else 1 for i in dic.values() ]
ans=1
for i in l:
    ans=ans*i%1000000007
print(ans)

Submission status: Accepted

Solution code:
import math
from collections import Counter

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

factor=[]
for f in range(2, math.ceil(math.sqrt(M))):
	while M % f == 0:
		factor.append(f)
		M //= f
if M > 1:
	factor.append(M)

def F(n):
	if n == 1:
		return n
	return n * F(n-1)

def G(n, k):
	if k == 1:
		return n
	return n * G(n-1, k-1)

def H(n, k):
	return G(n+k-1, k) // F(k)

ans = 1
for c in Counter(factor).values():
	ans *= H(N, c)
	ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

def power_mod(a,n):
    if n == 0:
        return 1
    x = (power_mod(a,n//2)**2)%MOD
    return x if n%2 == 0 else (a*x)%MOD

def inverse(a):
    return power_mod(a,MOD-2)

def comb(n,k):
    # k is small
    num = 1
    den = 1
    for i in range(1,k+1):
        num *= (n+1-i)
        den *= i
        num %= MOD
        den %= MOD
    return (num * inverse(den))%MOD

def solve(N,M,min_p=2):
    if M == 1:
        return 1
    for p in range(min_p, M+1):
        if p*p > M:
            # M is prime
            return N
        if M%p != 0:
            continue
        e = 0
        while M%p == 0:
            M //= p
            e += 1
        return (solve(N, M, p) * comb(N-1+e,e))%MOD
      
N,M = map(int, input().split())
ans = solve(N,M)

print(ans)

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce

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

def Pdeco(m):
    ret=[]
    for i in range(2,int((M)**(0.5))+100):
        if m<=i:
            if m!=1: ret.append(int(m))
            break
        elif i>int((M)**(0.5)+50):
            ret.append(m)
            break

        while m%i==0:
            m=m//i
            ret.append(i)
    return ret


def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

L=Pdeco(M)
nums=set(L)

for n in nums:
    p=L.count(n)
    ans=(ans*cmb(N+p-1,N-1))%P

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l={}
p=2

while m>=p*p:
    if m%p==0:
        if not p in l.keys():
            l[p]=0
        l[p]+=1
        m//=p
    else:
        p+=1
if not m in l.keys():
    l[m]=0
l[m] += 1

ans=1
for p,q in l.items():
    if p==1:
        continue
    for i in range(q):
        ans*=n+i
    for i in range(q):
        ans//=i+1

print(ans%1000000007)

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce

MOD = 10 ** 9 + 7

def get_soinnsuu(num):
    soinnsuu = []
    for i in range(2, int(num ** 0.5) + 2):
        now_time = 0
        if num < i:
            break
        while num % i == 0:
            now_time += 1
            num = num // i
        if now_time > 0:
            soinnsuu.append(now_time)
    if num > 1:
        soinnsuu.append(1)
    return soinnsuu


def comb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under


def start_process(N, M):
    soinnsuu = get_soinnsuu(M)
    ans = 1
    for ele in soinnsuu:
        ans *= int(comb(ele + N - 1, ele))
    # print(soinnsuu)
    print(ans % MOD)


def main():
    N, M = map(int, input().split())
    start_process(N, M)



if __name__ == '__main__':
    main()

Submission status: Accepted

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

MOD = 1000000007  # type: int

def get_factors(n):
    fact = 2
    tmp = n
    ret = []
    while fact * fact <= n:
        count = 0
        while tmp % fact == 0:
            tmp //= fact
            count += 1
        if count > 0:
            ret.append(count)
            #print(fact)
        fact += 1
    if tmp > 1:
        ret.append(1)
    return ret

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

def solve(N: int, M: int):
    facts = get_factors(M)
    #print(facts)
    ret = 1
    for c in facts:
        ret *= comb(c + N - 1, N - 1)
    print(ret % MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    solve(N, M)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from functools import reduce
from operator import mul

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):
    """
    組み合わせの数 nCr
    :param n:
    :param r:
    :return:
    """
    r = min(n - r, r)
    if r == 0:
        return 1
    return reduce(mul, range(n, n - r, -1)) // reduce(mul, range(r, 0, -1))
  
  
N,M = map(int, input().split())
m_factorized = factorize(M)
mod = 10 ** 9 + 7

ans = 1

    
for i in m_factorized:
  k = i[1] 
  ans *= cmb(N-1+k,k)
  ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import math
from collections import Counter

from scipy.misc import comb


def get_factors(n):
    """
    素因数分解
    :param int n:
    :type: list of int
    """
    if n <= 1:
        return []

    ret = []
    while n > 2 and n % 2 == 0:
        ret.append(2)
        n //= 2
    i = 3
    while i <= math.sqrt(n):
        if n % i == 0:
            ret.append(i)
            n //= i
        else:
            i += 2
    ret.append(n)
    return ret


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

factors = get_factors(m)
counts = Counter(factors)
# k**v を全部かけあわせたやつが m に一致する
# print(functools.reduce(operator.mul, [k ** v for k, v in counts.items()]))

# v 個の k を n 個の数に配分する組み合わせの数
# → v + (n-1) 個のスペースへの v の置き方の組み合わせの数
ans = 1
for k, v in counts.items():
    ans *= comb(v + (n - 1), v, exact=True)
    ans %= MOD
print(ans)