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: Runtime Error

Solution code:
import sys
import collections


def alg_duplicate_combination_mod(n, r, mod):
    n = n + r - 1
    r = min(n - r, r)
    if r == 0:
        return 1
    else:
        denominator = 1
        for i in range(n, n - r, -1):
            denominator = (denominator * i) % mod
        molecule = 1
        for i in range(1, r + 1):
            molecule = (molecule * i) % mod
        return denominator * pow(molecule, mod - 2, mod) % mod


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, input().rstrip('\n').split()))
    t = m
    d = collections.defaultdict(int)
    for i in range(2, int(t ** 0.5) + 1):
        while True:
            if t % i == 0:
                d[i] += 1
                t //= i
            else:
                break
    if t != 1:
        cnt *= alg_duplicate_combination_mod(n, v, od)
        cnt %= mod
    print(cnt)


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:

class Factorial:
    def __init__(self, n, mod=10**9+7):
        self.fac = [0] * (n+1)
        self.ifac = [0] * (n+1)
        self.fac[0] = 1
        self.ifac[0] = 1
        modmod = mod - 2
        for i in range(n):
            self.fac[i+1] = self.fac[i] * (i+1) % mod
            self.ifac[i+1] = self.ifac[i] * pow(i+1, modmod, mod) % mod

    def comb(self, n, r):
        if n == 0 and r == 0:
            return 1
        if n < r or n < 0:
            return 0
        tmp =  self.ifac[n-r] * self.ifac[r] % mod
        return tmp * self.fac[n] % mod

    def perm(self, n, r):
        if n == 0 and r == 0:
            return 1
        if n < r or n < 0:
            return 0
        return (self.fac[n] * self.ifac[n-r]) % mod

def make_divisors(n):
    divisors = {}
    tmp = n
    div = 2
    while n > 1 and div <= tmp**0.5:
        if n % div == 0:
            divisors[div] = 0
        while n % div == 0:
            n //= div
            divisors[div] += 1
        div += 1
    if n > 1:
        divisors[n] = 1
    return divisors

n,m = map(int, input().split())
mod = 10**9 + 7
divisors = make_divisors(m)
fact = Factorial(n + max(divisors.values()) + 1)

ans = 1
for value in divisors.values():
    ans = ans * fact.comb(value+n-1,value) % mod
print(ans)

Submission status: Runtime Error

Solution code:

def make_divisors(n):
    divisors = {}
    tmp = n
    div = 2
    while n > 1 and div <= tmp**0.5:
        if n % div == 0:
            divisors[div] = 0
        while n % div == 0:
            n //= div
            divisors[div] += 1
        div += 1
    if n > 1:
        divisors[n] = 1
    return divisors

def comb(n,r):
    if n == 0 and r == 0:
        return 1
    if n < r or n < 0:
        return 0
    tmp =  ifac[n-r] * ifac[r] % mod
    return tmp * fac[n] % mod

def perm(n,r):
    if n == 0 and r == 0:
        return 1
    if n < r or n < 0:
        return 0
    return fac[n] * ifac[n-r] % mod

def fact_init(n, mod=10**9+7):
    fac = [0] * (n+1)
    ifac = [0] * (n+1)
    fac[0] = 1
    ifac[0] = 1
    modmod = mod - 2
    for i in range(n):
        fac[i+1] = fac[i] * (i+1) % mod
        ifac[i+1] = ifac[i] * pow(i+1, modmod, mod) % mod
    return fac, ifac


n,m = map(int, input().split())
mod = 10**9 + 7
divisors = make_divisors(m)
fac, ifac = fact_init(n+max(divisors.values()) + 1)

ans = 1
for value in divisors.values():
    ans = ans * comb(value+n-1,value) % mod
print(ans % mod)

Submission status: Runtime Error

Solution code:
from collections import defaultdict as dd

N, M = map(int, input().split())
MOD = 10 ** 9 + 7
# a1 x a2 x .. x aN = M となる数列{ai}が何通りあるか
# まずは素因数分解
def make_prime_dict(x):
    primes = dd(int)
    check = 2
    while True:
        if x % check == 0:
            primes[check] += 1
            x = x // check
        else:
            check += 1
            if check > x:
                break
    return dict(primes)

primes = make_prime_dict(M)

Q = max(primes.values())
fact = [1]
fact_inv = [1]
for i in range(Q+N):
    new_fact = fact[-1] * (i+1) % MOD
    fact.append(new_fact)
    fact_inv.append(pow(new_fact, MOD - 2, MOD))

def mod_comb(n, r, mod):
    return fact[n] * fact_inv[n - r] % mod * fact_inv[r] % mod

res = 1
for q in primes.values():
    res *= mod_comb(q + N - 1, q, MOD)
    res %= MOD

print(res)

Submission status: Runtime Error

Solution code:
from collections import defaultdict as dd

N, M = map(int, input().split())
MOD = 10 ** 9 + 7
# a1 x a2 x .. x aN = M となる数列{ai}が何通りあるか
# まずは素因数分解
def make_prime_dict(x):
    primes = dd(int)
    check = 2
    while True:
        if x % check == 0:
            primes[check] += 1
            x = x // check
        else:
            check += 1
            if check > x:
                break
    return dict(primes)

primes = make_prime_dict(M)

Q = max(primes.values())
fact = [1]
fact_inv = [1]
for i in range(Q+N):
    new_fact = fact[-1] * (i+1) % MOD
    fact.append(new_fact)
    fact_inv.append(pow(new_fact, MOD - 2, MOD))

def mod_comb(n, r, mod):
    return fact[n] * fact_inv[n - r] % mod * fact_inv[r] % mod

res = 1
for q in primes.values():
    res *= mod_comb(q + N - 1, q, MOD)
    res %= MOD

print(res)
print(primes)

Submission status: Runtime Error

Solution code:
from collections import defaultdict as dd

N, M = map(int, input().split())
MOD = 10 ** 9 + 7
# a1 x a2 x .. x aN = M となる数列{ai}が何通りあるか
# まずは素因数分解
def make_prime_dict(x):
    primes = dd(int)
    check = 2
    while True:
        if x % check == 0:
            primes[check] += 1
            x = x // check
        else:
            check += 1
            if check > x:
                break
    return dict(primes)

primes = make_prime_dict(M)

Q = max(primes.values())
fact = [1]
fact_inv = [1]
for i in range(Q+N):
    new_fact = fact[-1] * (i+1) % MOD
    fact.append(new_fact)
    fact_inv.append(pow(new_fact, MOD - 2, MOD))

def mod_comb(n, r, mod):
    return fact[n] * fact_inv[n - r] % mod * fact_inv[r] % mod

res = 1
for q in primes.values():
    res *= mod_comb(q + N - 1, q, MOD) % MOD

print(res)

Submission status: Runtime Error

Solution code:
from collections import defaultdict as dd

N, M = map(int, input().split())
MOD = 10 ** 9 + 7
# a1 x a2 x .. x aN = M となる数列{ai}が何通りあるか
# まずは素因数分解
def make_prime_dict(x):
    primes = dd(int)
    check = 2
    while True:
        if x % check == 0:
            primes[check] += 1
            x = x // check
        else:
            check += 1
            if check > x:
                break
    return dict(primes)

primes = make_prime_dict(M)

fact = [1]
fact_inv = [1]
Q = max(primes.values())
for i in range(1, Q + N):
    fact.append(fact[-1] * i % MOD)
    fact_inv.append(fact_inv[-1] * pow(i, MOD - 2, MOD))

def mod_comb(n, r, mod):
    return fact[n] * fact_inv[n - r] % mod * fact_inv[r] % mod

res = 1
for q in primes.values():
    res *= mod_comb(q + N - 1, q, MOD) % MOD

print(res)

Submission status: Runtime Error

Solution code:
N = int(input())
p = 10**9 + 7

fac = [0] * (N + 33)
inv = [0] * (N + 33)
finv = [0] * (N + 33)

fac[0] = fac[1] = 1
inv[1] = 1
finv[0] = finv[1] = 1

for i in range(2, N+34):
  fac[i] = fac[i-1] * i % p
  inv[i] = p - inv[p%i] * (p // i) % p
  finv[i] = finv[i-1] * inv[i] % p

primes = {}
i = 2
n = N
while(n > 1):
  if(n % i == 0):
    primes[i] = primes.get(i, 0) + 1
    n //= i
  else:
    i += 2 - (n + 1) % 2

r = 1
for v in primes.value():
  r = r * fac[N+v-1] * finv[N-1] * finv[v] % p
print(r)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
h, w, d = map(int, input().split())
x = [None] * h * w
y = [[0] for _ in range(d)]
for i in range(h):
    r = [int(x) for x in input().split()]
    for j in range(w):
        x[r[j] - 1] = (i, j)
for i in range(d):
    for j in range(i + d, h * w, d):
        y[i].append(abs(x[j][0] - x[j - d][0]) + abs(x[j][1] - x[j - d][1]))
        y[i][-1] += y[i][-2]
for _ in range(int(input())):
    l, r = [int(x) - 1 for x in input().split()]
    m = l % d
    print(y[m][r // d] - y[m][l // d])

Submission status: Runtime Error

Solution code:
"""
8:30:00
"""

from collections import defaultdict
def getprime(n):
    if not isinstance(n, int):
        raise TypeError("Input int")
    if n < 2:
        raise ValueError("N >= 2")
    prime = []
    # 約数はsqrt(N)まで調べればOK
    data = [i+1 for i in range(1,n)]
    while True:
        p = data[0]
        if p >= int(n**0.5):
            return prime+data
        prime.append(p)
        # pで割り切れないものだけを残す
        data = [d for d in data if d%p != 0]

def factorization(n):
    factors = defaultdict(int)
    primes = getprime(int(n**0.5))
    for prime in primes:
        while n % prime == 0:
            factors[prime] += 1
            n //= prime
            # print(factors,n)
    if n != 1:
        factors[n] += 1
    return factors


def modconb(n,k,mod):
    # テーブルを作る
    fac = [0]*(n+1)
    finv = [0]*(n+1)
    inv = [0]*(n+1)  

    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1

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

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

"""
1 * 1 * 1のどこに素因数をかけるか
3^3だとして
どこかで3回3をかけないといけない
a + b + c = 3 //重複組合せ
3*3-1C3
こいつをかけ合わせると答えになる
modconbいる
"""

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

factors = factorization(m)
ans = 1
for k in factors.keys():
    x = factors[k]
    ans *= modconb(x+n-1,x,mod)
    ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def modfact(n):
    fact=[1]*(n+1)
    invfact=[1]*(n+1)
    for i in range(1,n+1):
        fact[i]=i*fact[i-1]%MOD
    invfact[n]=pow(fact[n],MOD-2,MOD)
    for i in range(n-1,-1,-1):
        invfact[i]=invfact[i+1]*(i+1)%MOD
    return fact,invfact

def prime_factorization(n):
    factor=[]
    sqrt=int(n**.5)
    for d in range(2,sqrt+1):
        while(n%d==0):
            n//=d
            factor.append(d)
    if n!=1: factor.append(n)
    return factor

def resolve():
    from collections import Counter
    n,m=map(int,input().split())
    if(n==1):
        print(1)
        return
        
    P=prime_factorization(m)
    C=Counter(P)
    C=list(C.values())

    N=max(C)
    fact,invfact=modfact(N+n)

    ans=1
    for v in C:
        ans*=fact[v+n-1]*invfact[n-1]*invfact[v]
        ans%=MOD
    print(ans)
resolve()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def modfact(n):
    fact=[1]*(n+1)
    invfact=[1]*(n+1)
    for i in range(1,n+1):
        fact[i]=i*fact[i-1]%MOD
    invfact[n]=pow(fact[n],MOD-2,MOD)
    for i in range(n-1,-1,-1):
        invfact[i]=invfact[i+1]*(i+1)%MOD
    return fact,invfact

def prime_factorization(n):
    factor=[]
    sqrt=int(n**.5)
    for d in range(2,sqrt+1):
        while(n%d==0):
            n//=d
            factor.append(d)
    if n!=1: factor.append(n)
    return factor

def resolve():
    from collections import Counter
    n,m=map(int,input().split())
    P=prime_factorization(m)
    C=Counter(P)
    C=list(C.values())

    N=max(C)
    fact,invfact=modfact(N+n)

    ans=1
    for v in C:
        ans*=fact[v+n-1]*invfact[n-1]*invfact[v]
        ans%=MOD
    print(ans)
resolve()

Submission status: Runtime Error

Solution code:
from math import factorial
from operator import mul
from functools import reduce

N, M = map(int, input().split())
A = [int(x) for x in input().split()]

dp = [-10**5]*(N+1)
dp[0] = 0
t = [0,2,5,5,4,5,6,3,7,6]

for i in range(2,N+1):
    for x in A:
        if i-t[x] >= 0:
            dp[i] = max(dp[i],dp[i-t[x]] + 1)

A.sort(reverse=True)
cur = ""
idx = N
while idx >0:
    for x in A:
        if idx - t[x] >= 0 and dp[idx] == dp[idx-t[x]] + 1:
            cur += str(x)
            idx -= t[x]
            break
print(cur)

Submission status: Runtime Error

Solution code:
def comb2(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 pff(m):
    pf = {}
    for i in range(2, int(m ** 0.5) + 1):
        while m % i == 0:
            pf[i] = pf.get(i, 0) + 1
            m //= i
    if m > 1: pf[m] = 1
    return pf

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


anst = int(1)
for i in L.values():
    anst *= comb2(i+N-1, i)
    anst = anst%1000000007

ans = anst
print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
mod=10**9+7
from operator import mul
from functools import reduce

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

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
lst=prime_factorize(m)
if m!=1:
    li=[1]
for i in range(1,len(lst)):
    if lst[i]==lst[i-1]:
        li[-1]+=1
    else:
        li.append(1)
ans=1
for u in li:
    a=n-1+u
    x=cmb(a,u)%mod
    ans=(ans*x)%mod
print(ans)

Submission status: Runtime Error

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def factorize(num: int) -> dict:
    """ 素因数分解 """
    from math import sqrt
    from collections import Counter

    d = Counter()
    # 終点はルート切り捨て+1
    for i in range(2, int(sqrt(num))+1):
        # 素因数分解：小さい方から割れるだけ割って素数をカウント
        while num % i == 0:
            num //= i
            d[i] += 1
        # 1まで分解したら終了
        if num == 1:
            break
    # 最後に残ったnumは素数(ただし1^1は1^0なので数に入れない)
    if num != 1:
        d[num] += 1
    return d

class FactInvMOD:
    """ 階乗たくさん使う時用のテーブル準備 """

    def __init__(self, MAX, MOD):
        """ MAX：階乗に使う数値の最大以上まで作る """
        
        MAX += 1
        self.MAX = MAX
        self.MOD = MOD
        # 階乗テーブル
        factorial = [1] * MAX
        factorial[0] = factorial[1] = 1
        for i in range(2, MAX):
            factorial[i] = factorial[i-1] * i % MOD
        # 階乗の逆元テーブル
        inverse = [1] * MAX
        # powに第三引数入れると冪乗のmod付計算を高速にやってくれる
        inverse[MAX-1] = pow(factorial[MAX-1], MOD-2, MOD)
        for i in range(MAX-2, 0, -1):
            # 最後から戻っていくこのループならMAX回powするより処理が速い
            inverse[i] = inverse[i+1] * (i+1) % MOD
        self.fact = factorial
        self.inv = inverse
    
    def nCr(self, n, r):
        """ 組み合わせの数 (必要な階乗と逆元のテーブルを事前に作っておく) """

        if n < r: return 0
        # 10C7 = 10C3
        r = min(r, n-r)
        # 分子の計算
        numerator = self.fact[n]
        # 分母の計算
        denominator = self.inv[r] * self.inv[n-r] % self.MOD
        return numerator * denominator % self.MOD

    def nPr(self, n, r):
        """ 順列 """

        if n < r: return 0
        return self.fact[n] * self.inv[n-r] % self.MOD

    def nHr(self, n, r):
        """ 重複組み合わせ """

        # r個選ぶところにN-1個の仕切りを入れる
        return self.nCr(r+n-1, r)

N, M = MAP()

d = factorize(M)
MAX = N + max(d.values())
fim = FactInvMOD(MAX, MOD)
ans = 1
for k, v in d.items():
    ans *= fim.nHr(N, v)
    ans %= MOD
print(ans)

Submission status: Runtime Error

Solution code:
def factorize(n):
    b,e = 2,0
    fct = []
    while b*b <= n:
        while n%b==0:
            n//=b
            e+=1
        if e>0:
            fct.append((b,e))
        b+=1
        e=0
    if n!=1:
        fct.append((n,1))
    return fct
    
N,M = list(map(int,input().split()))
 
pl = factorize(M)
 
max_coef=max([p[1] for p in pl])
 
 
if max_coef==0:
    print(N)
else:
 
    comb_list = [1]
    c = 1
    mod = 10**9+7
    for i in range(max_coef):
        c *= N+i
        c *= pow(i+1,mod-2,mod)
        c %= mod
        comb_list.append(c)
 
    ans = 1
 
    for p in pl:
        ans*=comb_list[p[1]]
        ans %= mod
 
    print(ans)

Submission status: Runtime Error

Solution code:
def factorize(n):
    b,e = 2,0
    fct = []
    while b*b <= n:
        while n%b==0:
            n//=b
            e+=1
        if e>0:
            fct.append((b,e))
        b+=1
    if n!=1:
        fct.append((n,1))
    return fct
    
N,M = list(map(int,input().split()))

pl = factorize(M)

max_coef=max([p[1] for p in pl])



if max_coef==0:
    print(N)
else:

    comb_list = [1]
    c = 1
    mod = 10**9+7
    for i in range(max_coef):
        c *= N+i
        c *= pow(i+1,mod-2,mod)
        c %= mod
        comb_list.append(c)

    ans = 1

    for p in pl:
        ans*=comb_list[p[1]]
        ans %= mod

    print(ans)

Submission status: Runtime Error

Solution code:
def factorize(n):
    b,e = 2,0
    fct = []
    while b*b < n:
        while n%b==0:
            n//=b
            e+=1
        if e>0:
            fct.append((b,e))
        b+=1
        e=0
    if n!=1:
        fct.append((n,1))
    return fct
    
N,M = list(map(int,input().split()))

pl = factorize(M)

max_coef=max([p[1] for p in pl])


if max_coef==0:
    print(N)
else:

    comb_list = [1]
    c = 1
    mod = 10**9+7
    for i in range(max_coef):
        c *= N+i
        c *= pow(i+1,mod-2,mod)
        c %= mod
        comb_list.append(c)

    ans = 1

    for p in pl:
        ans*=comb_list[p[1]]
        ans %= mod

    print(ans)

Submission status: Runtime Error

Solution code:
def sieve_of_eratosthenes(n):
    pl = [i for i in range(2, n + 1)] 
    i=0
    p = pl[0]
    while p**2<=n:
        pl = [pl[j] for j in range(len(pl)) if pl[j]%p!=0 or j<=i]
        i+=1
        p=pl[i]
    return pl

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

pl = sieve_of_eratosthenes(int(M**0.5))


m = M
coef_list = [0]*len(pl)
for i,p in enumerate(pl):
    if m==1:
        break
    while m%p==0:
        m//=p
        coef_list[i]+=1

max_coef=max(coef_list)

if max_coef==0:
    print(N)
else:

    comb_list = [1]
    c = 1
    mod = 10**9+7
    for i in range(max_coef):
        c *= N+i
        c *= pow(i+1,mod-2,mod)
        c %= mod
        comb_list.append(c)

    ans = 1

    for coef in coef_list:
        ans*=comb_list[coef]
        ans %= mod

    print(ans)

Submission status: Runtime Error

Solution code:
import collections
import math

MOD = 10**9 + 7


def eratosthenes(n):
    sieve = [True for _ in range(n + 1)]
    sieve[0] = False
    sieve[1] = False

    def _update(p):
        if sieve[p]:
            for i in range(p * 2, n + 1, p):
                sieve[i] = False

    if n > 1:
        _update(2)
    p = 3
    while p * p <= n:
        _update(p)
        p += 2
    return sieve


n, m = map(int, input().split())
mm = math.ceil(math.sqrt(m))
sieve = eratosthenes(mm)
primes = [i for i in range(mm) if sieve[i]]
counter = collections.Counter()
for p in primes:
    while m % p == 0:
        counter[p] += 1
        m //= p
    if m == 1:
        break
else:
    if m != 1:
        counter[m] += 1

me = max(counter.values())
factorials = [1]
for i in range(1, me + 1):
    factorials.append(factorials[-1] * i)

res = 1
for p, e in counter.items():
    for i in range(e):
        res *= e + n - 1 - i
    res //= factorials[e]
    res %= MOD
print(res)

Submission status: Runtime Error

Solution code:
import math
import collections

Max = 100001
Mod = 1000000007
fac = [0] * Max
finv = [0] * Max
inv = [0] * Max
def COMinit():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, Max):
        fac[i] = fac[i-1] * i % Mod 
        inv[i] = Mod - inv[Mod%i] * (Mod//i) % Mod
        finv[i] = finv[i-1] * inv[i] % Mod 

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

N, M = map(int, input().split())
prime_count = collections.Counter()
for i in range(2, math.ceil(math.sqrt(M))+1):
    while M % i == 0:
        M /= i
        prime_count[i] += 1
if M > 1:
    prime_count[M] += 1

ans = 1
COMinit()
for i, b in prime_count.items():
    tmp = COM(b+N-1, N-1)
    ans = (ans * tmp) % Mod 
print(ans)

Submission status: Runtime Error

Solution code:
import math

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

def trial_division(n):
  #素因数を格納するリスト
  factor = []
  #2から√n以下の数字で割っていく
  tmp = int(math.sqrt(n)) + 1
  for num in range(2,tmp):
    cnt = 0
    while n % num == 0:
      n //= num
      cnt += 1 
    if cnt != 0:
      factor.append(cnt)
  #リストが空ならそれは素数
  if not factor:
    return 'prime number'
  else:
    if n != 1:
      factor.append(1)
    return factor

from operator import mul
from functools import reduce

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

ans = 1
cnts = trial_division(M)
for cnt in cnts:
  ans = ans * (cmb(cnt+N-1, cnt))%MOD

print(ans)

Submission status: Runtime Error

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


def fact(x):
    a = []
    for i in range(2, int(x ** 0.5) + 1):
        if x % i == 0:
            j = 0
            while x % i == 0:
                x //= i
                j += 1
        a.append((i, j))
    if x != 1:
        a.append((x,1))
    return a


f = fact(m)


def conv(a, b):
    c = 1
    for i in range(b, b - a, -1):
        c *= i
    for i in range(1, a + 1):
        c //= i
    return c % (10 ** 9 + 7)


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

Submission status: Runtime Error

Solution code:
import sys
import math
input = sys.stdin.readline

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

    MOD = int(1e9) + 7

    kai = [1] * (N+1)
    for i in range(2, N+1):
        kai[i] = kai[i-1] * i
        kai[i] %= MOD

    MAX_PRIME = int(math.sqrt(M)) + 1
    primes = []
    is_prime = [True] * (MAX_PRIME+1)
    for i in range(2, MAX_PRIME+1):
        if is_prime[i]:
            primes.append(i)
            for j in range(2*i, MAX_PRIME+1, i):
                is_prime[j] = False
    
    insu = []

    tmp = M
    max_count = 0
    for i in range(len(primes)):
        count = 0
        while tmp%primes[i] == 0:
            tmp //= primes[i]
            count += 1
        if count > 0:
            insu.append((primes[i], count))
            max_count = max(max_count, count)
    # print(insu)
    
    max_c = min(max_count, N)
    n_c = [1] * (max_c + 1)

    for i in range(1, max_c+1):
        n_c[i] = kai[N] * pow(kai[N-i], MOD-2, MOD) * pow(kai[i], MOD-2, MOD)

    ans = 1
    for p, c in insu:
        # print(p, c)
        tmp = 0
        for i in range(1, min(max_c, c)+1):
            tmp += n_c[i] * kai[c-1] * pow(kai[c-i], MOD-2, MOD) * pow(kai[i-1], MOD-2, MOD)
            tmp %= MOD
        if tmp > 0:
            ans *= tmp
            ans %= MOD
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
import math
input = sys.stdin.readline

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

    MOD = int(1e9) + 7

    kai = [1] * (N+1)
    for i in range(2, N+1):
        kai[i] = kai[i-1] * i
        kai[i] %= MOD

    MAX_PRIME = int(math.sqrt(M)) + 1
    primes = []
    is_prime = [True] * (MAX_PRIME+1)
    for i in range(2, MAX_PRIME+1):
        if is_prime[i]:
            primes.append(i)
            for j in range(2*i, MAX_PRIME+1, i):
                is_prime[j] = False
    
    insu = []

    tmp = M
    max_count = 0
    for i in range(len(primes)):
        count = 0
        while tmp%primes[i] == 0:
            tmp //= primes[i]
            count += 1
        if count > 0:
            insu.append((primes[i], count))
            max_count = max(max_count, count)
    # print(insu)
    
    max_c = min(max_count, N)
    n_c = [1] * (max_c + 1)

    for i in range(1, max_c+1):
        n_c[i] = kai[N] * pow(kai[N-i], MOD-2, MOD) * pow(kai[i], MOD-2, MOD)

    ans = 1
    for p, c in insu:
        # print(p, c)
        tmp = 0
        for i in range(1, min(max_c, c)+1):
            tmp += n_c[i] * kai[c-1] * pow(kai[c-i], MOD-2, MOD) * pow(kai[i-1], MOD-2, MOD)
            tmp %= MOD
        ans *= tmp
        ans %= MOD
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
import math
input = sys.stdin.readline

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

    MOD = int(1e9) + 7

    kai = [1] * (N+1)
    for i in range(2, N+1):
        kai[i] = kai[i-1] * i
        kai[i] %= MOD

    MAX_PRIME = int(math.sqrt(M)) + 1
    primes = []
    is_prime = [True] * (MAX_PRIME+1)
    for i in range(2, MAX_PRIME+1):
        if is_prime[i]:
            primes.append(i)
            for j in range(2*i, MAX_PRIME+1, i):
                is_prime[j] = False
    
    insu = []

    tmp = M
    max_count = 0
    for i in range(len(primes)):
        count = 0
        while tmp%primes[i] == 0:
            tmp //= primes[i]
            count += 1
        if count > 0:
            insu.append((primes[i], count))
            max_count = max(max_count, count)
    # print(insu)
    
    max_c = min(max_count, N)
    n_c = [1] * (max_c + 1)

    for i in range(1, max_c+1):
        n_c[i] = kai[N] * pow(kai[N-i], MOD-2, MOD) * pow(kai[i], MOD-2, MOD)

    ans = 1
    for p, c in insu:
        tmp = 0
        for i in range(1, c+1):
            tmp += n_c[i] * kai[c-1] * pow(kai[c-i], MOD-2, MOD) * pow(kai[i-1], MOD-2, MOD)
            tmp %= MOD
        ans *= tmp
        ans %= MOD
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import math
import collections

from operator import mul
from functools import reduce

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**4
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 = list(map(int,input().split()))

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

c = collections.Counter(prime_factorize(M))
#print(c)
ans = 1
for i,j in c.items():
    ans *= cmb(N+j-1,j,mod) % mod
print(int(ans%mod))

Submission status: Runtime Error

Solution code:
import math
import collections

from operator import mul
from functools import reduce

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**4
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 = list(map(int,input().split()))

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

c = collections.Counter(prime_factorize(M))
#print(c)
ans = 1
for i,j in c.items():
    ans *= cmb(N+j-1,j,mod)
print(int(ans%mod))

Submission status: Runtime Error

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

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


mod = 10**9+7 #出力の制限
N = n + 100
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 )

#print(combo(2,1))


fac = [0] * (m+1)
mm = m
for i in range(2,m+1):
    while mm % i == 0:
        mm = mm // i
        fac[i] += 1
        #print(mm,fac)

count = 1

for i in range(2,m+1):
    if fac[i] >= 1:
        count = (count * cmb(fac[i]+n-1,fac[i],mod)) % mod
    #print(count)
    
print(count)

Submission status: Runtime Error

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

def combo(p,q):
    if p == 0:
        return 1
    elif q == 0 or q == p:
        return 1
    else:
        ret = (combo(p-1,q-1) + combo(p-1,q)) % MOD
        return ret

#print(combo(2,1))


fac = [0] * (m+1)
mm = m
for i in range(2,m+1):
    while mm % i == 0:
        mm = mm // i
        fac[i] += 1
        #print(mm,fac)

count = 1

for i in range(2,m+1):
    if fac[i] >= 1:
        count = (count * combo(fac[i]+n-1,fac[i])) % MOD
    #print(count)
    
print(count)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
memo = [{} for _ in range(n+30)]
MOD = 10 ** 9 + 7

def combo(p,q):
    if p == 0:
        return 1
    elif q == 0 or q == p:
        return 1
    elif q in memo[p]:
        return memo[p][q]
    else:
        ret = (combo(p-1,q-1) + combo(p-1,q)) % MOD
        memo[p][q] = ret
        return ret

#print(combo(2,1))


fac = [0] * (m+1)
mm = m
for i in range(2,m+1):
    while mm % i == 0:
        mm = mm // i
        fac[i] += 1
        #print(mm,fac)

count = 1

for i in range(2,m+1):
    if fac[i] >= 1:
        count = (count * combo(fac[i]+n-1,fac[i])) % MOD
    #print(count)
    
print(count)