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:
N, M = list(map(int, input().split()))

MOD = 10**9+7

class Comb:
    def __init__(self, N):
        self.fac = [1] * (N+1)
        for i in range(2, N+1): self.fac[i] = self.fac[i-1] * i % MOD

    def pow(self, a, b):
        res = 1
        while b:
            if b & 1: res = res * a % MOD
            a = a**2 % MOD
            b >>= 1
        return res

    def comb(self, n, r):
        if r < 0 or r > n: return 0
        return (self.fac[n] * self.pow(self.fac[r], MOD-2)) % MOD * self.pow(self.fac[n-r], MOD-2) % MOD

    def permutation(self, n, r):
        if r == 0: return 1
        return self.fac[n] * self.pow(self.fac[n-r], MOD-2) % MOD

from collections import *
def get_prime(n):
    c = Counter()

    while not n % 2:
        c[2] += 1
        n //= 2
    i = 3

    while i <= n**0.5:
        while not n % i:
            c[i] += 1
            n //= i
        i += 2

    while not n % i:
        c[i] += 1
        n //= i

    return c

prime = get_prime(M)
comb = Comb(N+max([m for m in prime.values()]))

ans = 1

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict
def factorization(n):
    arr = {}
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr[i] = cnt

    if temp != 1:
        arr[temp] = 1
    #if len(arr.keys()) == 0:
    #    arr[n] = 1
    return arr


def prepare(n, MOD):

    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return factorials, invs

import math
from itertools import combinations
from collections import Counter
MOD = 1000000007

def solve():
    N, M = map(int, input().split())
    temp = factorization(M)
    #print(temp)
    max_num = max(temp.values())
    factorials, invs = prepare(N+max_num-1, MOD)
    #print(factorials, invs)
    ans = 1
    for i, j in temp.items():
        ans *= factorials[N+j-1]
        ans %= MOD
        ans *= invs[N-1]
        ans %= MOD
        ans *= invs[j]
        ans %= MOD
        #print(ans)
    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])
    if temp != 1:
        arr.append([temp, 1])
    if arr == []:
        arr.append([n, 1])
    return arr


def prepare(n, MOD):

    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return factorials, invs

import math
from itertools import combinations
from collections import Counter
MOD = 1000000007

def solve():
    N, M = map(int, input().split())
    factorials, invs = prepare(N, MOD)
    #print(factorials, invs)
    temp = factorization(M)
    nums = []
    for i, j in temp:
        for k in range(j):
            nums.append(i)
    #print(nums)

    divisors = set()
    for i in range(1, len(nums)+1):
        for temp in combinations(nums, i):
            y = 1
            for x in temp:
                y = y * x
            divisors.add(y)
    #print(divisors)

    pattern = set()
    for x in divisors:
        m = M // x
        temp_m = factorization(m)
        nums_m = []
        for i, j in temp_m:
            for k in range(j):
                nums_m.append(i)
        nums_m.append(x)
        nums_m.sort()
        pattern.add(tuple(nums_m))
    #print(pattern)

    ans = 0
    fact_N = factorials[N]
    for x in pattern:
        if 1 in x:
            ones = (N-len(x)) + 1
            cnt = Counter(list(x))
            #print(cnt)
            perm = fact_N * invs[ones]
            #print(perm)
        else:
            ones = (N-len(x))
            cnt = Counter(list(x))
            #print(cnt)
            perm = fact_N
            for value in cnt.values():
                perm = perm * invs[value]
            perm = perm * invs[ones]
            #print(perm)
        ans += perm
    print(ans % MOD)

if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])
    if temp != 1:
        arr.append([temp, 1])
    if arr == []:
        arr.append([n, 1])
    return arr


def prepare(n, MOD):

    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return factorials, invs

import math
from itertools import combinations
from collections import Counter
MOD = 1000000007

def solve():
    N, M = map(int, input().split())
    factorials, invs = prepare(N, MOD)
    #print(factorials, invs)
    temp = factorization(M)
    nums = []
    for i, j in temp:
        for k in range(j):
            nums.append(i)
    #print(nums)

    divisors = set()
    for i in range(1, len(nums)+1):
        for temp in combinations(nums, i):
            y = 1
            for x in temp:
                y = y * x
            divisors.add(y)
    #print(divisors)

    pattern = set()
    for x in divisors:
        m = M // x
        temp_m = factorization(m)
        nums_m = []
        for i, j in temp_m:
            for k in range(j):
                nums_m.append(i)
        nums_m.append(x)
        nums_m.sort()
        pattern.add(tuple(nums_m))
    #print(pattern)

    ans = 0
    fact_N = factorials[N]
    for x in pattern:
        if 1 in x:
            ones = (N-len(x)) + 1
            cnt = Counter(list(x))
            print(cnt)
            perm = fact_N * invs[ones]
            print(perm)
        else:
            ones = (N-len(x))
            cnt = Counter(list(x))
            print(cnt)
            perm = fact_N
            for value in cnt.values():
                perm = perm * invs[value]
            perm = perm * invs[ones]
            print(perm)
        ans += perm
    print(ans % MOD)

if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
from collections import defaultdict as dd
import sys
import math
n, m = map(int, input().split())
dic = dd(int)

#M=1
if m == 1:
    print(1)
    sys.exit()
elif n == 1:
    print(1)
    sys.exit()

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

for i in range(2, math.ceil(m**0.5) + 3):
    while m % i == 0:
        m //= i
        dic[i] += 1
else:
    m != 1:
        dic[m] = 1
#print(dic)

ans = 1
mod = 10**9 + 7
for count in dic.values():
    ans *= combinations_count(count + n - 1, n-1) % mod

print(ans % mod)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    n, m = map(int, input().split())
    # https://atcoder.jp/contests/abc156/submissions/11621672
    def modpow(a, b, mod=10 ** 9 + 7):
        ret = 1
        while b > 0:
            if b % 2 == 1:
                ret = ret * a % mod
            a = a * a % mod
            b //= 2
        return ret


    def modcomb(n, c, mod=10 ** 9 + 7):
        if n<c:
            return 0
        if c > n - c:
            c = n - c
        u, d = 1, 1
        for i in range(c):
            u = u * (n - i) % mod
            d = d * (i + 1) % mod
        return u * modpow(d, mod - 2) % mod


    """mod = 10 ** 9 + 7
    n, a, b = map(int, input().split())
    ans = (modpow(2, n) - 1) % mod
    ans = (ans-modcomb(n, a)) % mod
    ans = (ans-modcomb(n, b)) % mod
    print(ans)"""

    # combどうしの積をとると余りがずれるので避ける！　普通のcombを計算して最後にmodをとって。

    import math

    # cf. https://qiita.com/suecharo/items/14137fb74c26e2388f1f
    def make_prime_list_2(num):
        if num < 2:
            return []

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

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

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

        return [prime for prime in prime_list if prime != 0]

    def prime_factorization_2(num):
        """numの素因数分解
        素因数をkeyに乗数をvalueに格納した辞書型dict_counterを返す"""

        if num <= 1:
            return False
        else:
            num_sqrt = math.floor(math.sqrt(num))
            prime_list = make_prime_list_2(num_sqrt)

            dict_counter = {}  # 何度もこの関数を呼び出して辞書を更新したい時はこれを引数にして
            # cf. https://atcoder.jp/contests/arc034/submissions/12251452

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

            return dict_counter

    ans = 1
    d = prime_factorization_2(m)
    mod = 10 ** 9 + 7

    for k, v in d.items():
        ans = ans * modcomb(v + n - 1, n - 1)
    print(ans % mod)


resolve()

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    n, m = map(int, input().split())
    # https://atcoder.jp/contests/abc156/submissions/11621672
    def modpow(a, b, mod=10 ** 9 + 7):
        ret = 1
        while b > 0:
            if b % 2 == 1:
                ret = ret * a % mod
            a = a * a % mod
            b //= 2
        return ret


    def modcomb(n, c, mod=10 ** 9 + 7):
        if c > n - c:
            c = n - c
        u, d = 1, 1
        for i in range(c):
            u = u * (n - i) % mod
            d = d * (i + 1) % mod
        return u * modpow(d, mod - 2) % mod


    """mod = 10 ** 9 + 7
    n, a, b = map(int, input().split())
    ans = (modpow(2, n) - 1) % mod
    ans = (ans-modcomb(n, a)) % mod
    ans = (ans-modcomb(n, b)) % mod
    print(ans)"""

    # combどうしの積をとると余りがずれるので避ける！　普通のcombを計算して最後にmodをとって。

    import math

    # cf. https://qiita.com/suecharo/items/14137fb74c26e2388f1f
    def make_prime_list_2(num):
        if num < 2:
            return []

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

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

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

        return [prime for prime in prime_list if prime != 0]

    def prime_factorization_2(num):
        """numの素因数分解
        素因数をkeyに乗数をvalueに格納した辞書型dict_counterを返す"""

        if num <= 1:
            return False
        else:
            num_sqrt = math.floor(math.sqrt(num))
            prime_list = make_prime_list_2(num_sqrt)

            dict_counter = {}  # 何度もこの関数を呼び出して辞書を更新したい時はこれを引数にして
            # cf. https://atcoder.jp/contests/arc034/submissions/12251452

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

            return dict_counter

    ans = 1
    d = prime_factorization_2(m)
    mod = 10 ** 9 + 7

    for k, v in d.items():
        ans = ans * modcomb(v + n - 1, n - 1)
    print(ans % mod)


resolve()

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


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

    def framod(n, mod=10 ** 9 + 7, a=1):
        for i in range(1, n + 1):
            a = a * i % mod
        return a

    def power(n, r, mod=10 ** 9 + 7):
        if r == 0: return 1
        if r % 2 == 0:
            return power(n * n % mod, r // 2, mod) % mod
        if r % 2 == 1:
            return n * power(n, r - 1, mod) % mod

    def comb(n, k, mod=10 ** 9 + 7):
        a = framod(n, mod)
        b = framod(k, mod)
        c = framod(n - k, mod)
        return (a * power(b, mod - 2, mod) * power(c, mod - 2, mod)) % mod

    # combどうしの積をとると余りがずれるので避ける！　普通のcombを計算して最後にmodをとって。
    import math

    # cf. https://qiita.com/suecharo/items/14137fb74c26e2388f1f
    def make_prime_list_2(num):
        if num < 2:
            return []

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

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

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

        return [prime for prime in prime_list if prime != 0]

    def prime_factorization_2(num):
        """numの素因数分解
        素因数をkeyに乗数をvalueに格納した辞書型dict_counterを返す"""

        if num <= 1:
            return False
        else:
            num_sqrt = math.floor(math.sqrt(num))
            prime_list = make_prime_list_2(num_sqrt)

            dict_counter = {}  # 何度もこの関数を呼び出して辞書を更新したい時はこれを引数にして
            # cf. https://atcoder.jp/contests/arc034/submissions/12251452

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

            return dict_counter

    ans = 1
    d = prime_factorization_2(m)
    mod = 10 ** 9 + 7

    for k, v in d.items():
        ans = ans * comb(v + n - 1, n - 1)
    print(ans % mod)


resolve()

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


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

    def framod(n, mod=10 ** 9 + 7, a=1):
        for i in range(1, n + 1):
            a = a * i % mod
        return a

    def power(n, r, mod=10 ** 9 + 7):
        if r == 0: return 1
        if r % 2 == 0:
            return power(n * n % mod, r // 2, mod) % mod
        if r % 2 == 1:
            return n * power(n, r - 1, mod) % mod

    def comb(n, k, mod=10 ** 9 + 7):
        a = framod(n, mod)
        b = framod(k, mod)
        c = framod(n - k, mod)
        return (a * power(b, mod - 2, mod) * power(c, mod - 2, mod)) % mod

    # combどうしの積をとると余りがずれるので避ける！　普通のcombを計算して最後にmodをとって。
    import math

    # cf. https://qiita.com/suecharo/items/14137fb74c26e2388f1f
    def make_prime_list_2(num):
        if num < 2:
            return []

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

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

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

        return [prime for prime in prime_list if prime != 0]

    def prime_factorization_2(num):
        """numの素因数分解
        素因数をkeyに乗数をvalueに格納した辞書型dict_counterを返す"""

        if num <= 1:
            return False
        else:
            num_sqrt = math.floor(math.sqrt(num))
            prime_list = make_prime_list_2(num_sqrt)

            dict_counter = {}  # 何度もこの関数を呼び出して辞書を更新したい時はこれを引数にして
            # cf. https://atcoder.jp/contests/arc034/submissions/12251452

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

            return dict_counter

    ans = 1
    d = prime_factorization_2(m)
    mod = 10 ** 9 + 7

    for k, v in d.items():
        ans = ans*comb(v+n - 1, n - 1)%mod
    print(ans % mod)


resolve()

Submission status: Runtime Error

Solution code:
from scipy.special import comb as cmb
n, m = map(int, input().split())

mod = 10 ** 9 + 7
N = 100005

# #逆元テーブル
# inv_t = [0]+[1]
# for i in range(2, N):
#   inv_t += [inv_t[mod % i] * (mod - int(mod / i)) % mod]

# #階乗計算
# kai = [1, 1]
# rev_kai = [1, inv_t[1]]
# for i in range(2, N):
# 	kai.append(kai[-1] * i % mod)
# 	rev_kai.append(rev_kai[-1] * inv_t[i] % mod)

# # コンビネーション計算
# def cmb(n, r):
# 	return kai[n] * rev_kai[r] * rev_kai[n-r] % mod

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

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

    return arr

ans = 1

for _, cnt in factorization(m):
    ans = ans * int(cmb(cnt + n - 1, n - 1, exact=True)) % mod

print(ans)

Submission status: Runtime Error

Solution code:
"""
---アルゴリズム概要---
Mを構成する素因数を、a1~aNの各スロットにいくつ置くのか、を考える問題。
まずは試し割りによってMを素因数分解。
重複組合せの公式で各素因数の配置パターンを算出し累乗していく。

試し割りは、O(√M)の計算量で処理できる。
√Mを超える素因数は、多くても一つしか存在しないため、√Mを超える値で試し割りをする必要はない。
もし√Mまでの値で試し割りを終えた段階で、Mを素因数分解しきれていなければ、残った商こそが√Mを超える唯一の素因数である。

簡単に証明
もし√Mを超える素因数が２つ存在しているとしよう。
それらは、(√M + α)と(√M + β)というふうに表すことができる。
この２つの積は明らかにMの値を超えてしまう。つまり前提に矛盾する。
したがって、√Mを超える素因数は多くても一つ
"""
from collections import Counter
import math

N,M = map(int,input().split())
factors = []

while M%2 == 0:
    M//=2
    factors.append(2)
    
f = 3
while f**2 <= M:
    while M%f==0:
        M//=f
        factors.append(f)
    f+=2
if M!=0:
    factors.append(M)

factors = Counter(factors)

ans = 1
for k in factors.values():
    ans *= math.factorial(k+N-1)//(math.factorial(N-k)*math.factorial(k))

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

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
l = []
i = 2
while m != 1:
    if m%i == 0:
        l.append(0)
        while m%i == 0:
            l[-1] += 1
            m //= i
    i += 1

mod = 10**9+7 
fact = [1,1]
finv = [1,1]
inv = [0,1]
 
for i in range(2,n+max(l)+5):
    fact.append((fact[-1]*i)%mod)
    inv.append((inv[mod%i]*(mod-mod//i))%mod)
    finv.append((finv[-1]*inv[-1])%mod)
 
def nCr(n,r,mod):
    if r > n:
        return 0
    else: 
        return fact[n]*finv[r]*finv[n-r]%mod

ans = 1

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

Submission status: Runtime Error

Solution code:
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr
  
n,m = map(int,input().split())
chk = factorization(m)
#print(chk)
def make_array_for_comb(N, mod=10**9+7):
    fact = [1,1]
    fact_inv = [1,1]
    inv = [0,1]
    for i in range(2, N+1):
        fact.append((fact[-1]*i) % mod)
        inv.append((-inv[mod%i] * (mod//i)) % mod)
        fact_inv.append((fact_inv[-1]*inv[i]) % mod)
    return fact, fact_inv

def comb(n, r, mod=10**9+7):
  if (r < 0) or (n < r):
      return 0
  r = min(r, n - r)
  return fact[n] * fact_inv[r] * fact_inv[n-r] % mod

mod = 10**9+7
fact, fact_inv = make_array_for_comb(n,mod)
ans = 1
for i in chk:
  ans *= comb(i[1]+n-1,i[1],mod)
  ans %= mod
if m == 1:
  ans = 1
print(ans)

Submission status: Runtime Error

Solution code:
import math
def findFactors(n):
    now=n
    f=[]
    while now%2==0:
        now//=2
        f.append(2)
    p=3
    while p<=math.sqrt(n):
        while now%p==0:
            now//=p
            f.append(p)
        p+=2
        if now==1:
            break
    if now>math.sqrt(n):
        f.append(now)
    return f

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

mod=10**9+7
N=10**5+100
g1=[1,1]
g2=[1,1]
inverse=[0,1]

#n!とその逆元を求めておく
for i in range(2,N+1):
    g1.append((g1[-1]*i)%mod)
    inverse.append((-inverse[mod%i]*(mod//i))%mod)
    g2.append((g2[-1]*inverse[-1])%mod)

n,m=map(int,input().split())
F=findFactors(m)
ans=1

now=F[0]
cnt=0
for f in F:
    if f==now:
        cnt+=1
    else:
        ans*=cmb(n-1+cnt,cnt)
        ans%=mod
        now=f
        cnt=1
ans*=cmb(n-1+cnt,cnt)
ans%=mod
print(ans)

Submission status: Runtime Error

Solution code:
import math
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

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

    return arr
def cmb(n, r):
    if n < 0 or r < 0:
        return 0
    if r > n:
        return 0
 
    r = min(n-r, r)
    res = 1
    for i in range(r):
        res *= n - i
n, m = map(int, input().split())
b = [x[1] for x in factorization(m)]
ans = 1
for i in b:
  c = cmb(n+i-1, i)
  ans = ans * c
print(ans%(10**9+7))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
mod=10**9+7
N=10**5+1+20
p=[1]*N #assume all are primes from start 
for i in range(2,N):
    if p[i]==1:
        for j in range(2*i,N,i):
            p[j]=0
primes=[]
for i in range(2,N):
    if p[i]==1:
        primes.append(i)

#print(primes)
fact=[1]*N
for i in range(2,N):
    fact[i]=(i*fact[i-1])%mod
ifact=[0]*N
ifact[N-1]=pow(fact[N-1],mod-2,mod)
for i in range(N-2,0,-1):
    ifact[i]=((i+1)*ifact[i+1])%mod
ans=1
for x in primes:
    if x>m:
        break
    cnt=0
    #print(m,end=' before\n')
    while m%x==0:
        m//=x
        cnt+=1
    if cnt==0:
        continue
    #print(x,cnt)
    #print(m,end=' after\n')
    
    val=(fact[n-1+cnt]*(ifact[cnt]*ifact[n-1])%mod)%mod
    ans=(ans*val)%mod
if m>1:
    ans=(ans*n)%mod
print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
mod=10**9+7
N=10**5+1+20
p=[1]*N #assume all are primes from start 
for i in range(2,N):
    if p[i]==1:
        for j in range(2*i,N,i):
            p[j]=0
primes=[]
for i in range(2,N):
    if p[i]==1:
        primes.append(i)

#print(primes)
fact=[1]*N
for i in range(2,N):
    fact[i]=(i*fact[i-1])%mod
ifact=[0]*N
ifact[N-1]=pow(fact[N-1],mod-2,mod)
for i in range(N-2,0,-1):
    ifact[i]=((i+1)*ifact[i+1])%mod
ans=1
for x in primes:
    if x>m:
        break
    cnt=0
    #print(m,end=' before\n')
    while m%x==0:
        m//=x
        cnt+=1
    if cnt==0:
        continue
    #print(x,cnt)
    #print(m,end=' after\n')
    
    val=(fact[n-1+cnt]*(ifact[cnt]*ifact[n-1])%mod)%mod
    ans=(ans*val)%mod
if m>1:
    cnt=1
    val=(fact[n-1+cnt]*(ifact[cnt]*ifact[n-1])%mod)%mod
    ans=(ans*val)%mod
print(ans)

Submission status: Runtime Error

Solution code:
mod = 10**9+7
def sieve(N):#エラトステネスの篩
    prime = [0]*(N+1)
    isprime = [True]*(N+1)
    isprime[0]=isprime[1] = False
    num = 0
    for p in range(2,N+1):
        if isprime[p]:
            prime[num] = p
            num += 1
            for j in range(2*p,N+1,p):
                isprime[j] = False
    prime.sort()
    prime.reverse()
    for k in range(N-1):
        if prime[k+1] == 0:
            end = k
            break
    return prime[:end+1]

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

def solve():
    N,M = map(int,input().split())
    if M == 1:
        print(1)
    prime = sieve(M)
    prime.sort()
    b = {}
    for i in prime:
        if M%i == 0:
            cnt = 0
            while M%i == 0:
                cnt += 1
                M //= i
            b[i] = cnt
    ans = 1
    for num in b:
        ans *= comb(b[num]+N-1,b[num])
        ans %= mod
    print(ans)

if __name__=="__main__":
    solve()

Submission status: Runtime Error

Solution code:
def prime_factorize(n):
    ans = []
    for i in range(2, int(n ** (1 / 2)) + 1):
        while True:
            if not n % i == 0:
                break
            ans.append(i)
            n /= i
        if n == 1:
            break
    if n != 1:
        ans.append(int(n))
    return ans

def comb(n, r, p):
    x, y = 1, 1
    for i in range(n, n - r, -1):
        x *= i
        y *= i + r - n
        x %= p
        y %= p
    return pow(y, p - 2, p) * x % p

n, m = map(int, input().split())
mod = 10 ** 9 + 7
s = prime_factorize(m)
c = 0
d = s[0]
ans = 1
for i in range(len(s)):
    if d == s[i]:
        c += 1
    else:
        d = s[i]
        ans *= comb(n - 1 + c, c, mod)
        ans %= mod
        c = 1
ans *= comb(n - 1 + c, c, mod)
ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""


mod = 10**9+7 #出力の制限
N = 10**5+10**4
def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
def p(n,r):
    if ( r<0 or r>n ):
        return 0
    return g1[n] * g2[n-r] % mod

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 )
# a = cmb(n,r)

N,M = m()

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

def make_divisors(n): #約数列挙
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

po = prime_decomposition(M)

po = s(po)


co = 1


for i in range(len(po)):
    co *= cmb(po[i][1]+N-1,N-1)
    co %= mod
print(co)

Submission status: Runtime Error

Solution code:
class Factorial():
    def __init__(self,n,mod):
        self.mod = mod
        self.factorial = [0 for _ in range(n+1)]
        self.inv = [0 for _ in range(n+1)]
        self.factorial[0] = 1
        self.inv[0] = 1
        for i in range(n):
            self.factorial[i+1] = self.factorial[i]*(i+1)%mod
        self.inv[n] = pow(self.factorial[n],mod-2,mod)
        for i in range(n)[::-1]:
            self.inv[i] = self.inv[i+1]*(i+1)%mod
            
    def comb(self,m,k):
        return self.factorial[m]*self.inv[k]*self.inv[m-k]%self.mod

def factorization(n):
    if n == 1: return [1]
    res = []
    x = n
    y = 2
    while y*y <= x:
        while x % y == 0:
            res.append(y)
            x //= y
        y += 1
    if x > 1: res.append(x)
    return res

from collections import Counter

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

ans = 1

if M > 1:

    F = factorization(M)
    C = Counter(F)

    fact = Factorial(2*N,MOD)
    
    for v in C.values():
        ans *= fact.comb(N+v-1,v)
        ans %= MOD

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
from operator import mul
from functools import reduce
import math

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

factor = {}
n = M
f = 2
while n > 1:
    if n%f == 0:
        if not f in factor:
            factor[f] = 1
        else:
            factor[f] += 1
        n = n//f
        continue
    f += 1
#print(factor)

max_v = max(factor.values())

def comb(n,r):
    nk = reduce(mul, range(n, n-r, -1), 1)
    rk = reduce(mul, range(1, r+1), 1)
    return nk//rk

ans = 1
fac_list = [1]
for i in range(2, max_v+N):
    fac_list.append(i*fac_list[-1])

for i in factor.values():
    ans *= fac_list[i+N-2]//(fac_list[i-1]*fac_list[N-2])
    #ans *= comb(i+N-1, N-1)
print(int(ans)%(10**9+7))