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: Time Limit Exceeded

Solution code:
from functools import lru_cache


@lru_cache()
def mod_power(a, f_power):
    """
    a の p 乗を求めるアルゴリズム
    計算量はO(log(f_power))
    """
    if f_power == 0:
        return 1
    if f_power % 2 == 0:
        half = mod_power(a, f_power / 2)
        # half : a ** (power /2) の 2乗で a ** power を求める
        return half * half % MOD
    else:
        return a * mod_power(a, f_power - 1) % MOD


@lru_cache()
def comb(a, b):
    if b > a - b:
        return comb(a, a - b)
    # res = 1
    mul = 1
    div = 1
    for i in range(b):
        # res *= (a - i)
        # res /= (i + 1)
        mul *= (a - i)
        mul %= MOD

        div *= (i + 1)
        div %= MOD
    res = mul * mod_power(div, MOD - 2) % MOD
    return res


def prime_factorization(x):
    res = []
    i = 2
    left = x + 0
    while True:
        if (i * i > x) and (left == 1):
            break
        cnt = 0
        while left % i == 0:
            left /= i
            cnt += 1
        if cnt > 0:
            res.append(cnt)
        # print(i, res)
        i += 1
    return res


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

MOD = 10 ** 9 + 7

ans = 1
for power in prime_factorization(m):
    ans *= comb(n - 1 + power, power)
ans %= MOD

print(ans)
# print(prime_factorization(6))

Submission status: Time Limit Exceeded

Solution code:
def mod_power(a, f_power):
    """
    a の p 乗を求めるアルゴリズム
    計算量はO(log(f_power))
    """
    if f_power == 0:
        return 1
    if f_power % 2 == 0:
        half = mod_power(a, f_power / 2)
        # half : a ** (power /2) の 2乗で a ** power を求める
        return half * half % MOD
    else:
        return a * mod_power(a, f_power - 1) % MOD


def comb(a, b):
    if b > a - b:
        return comb(a, a - b)
    # res = 1
    mul = 1
    div = 1
    for i in range(b):
        # res *= (a - i)
        # res /= (i + 1)
        mul *= (a - i)
        mul %= MOD

        div *= (i + 1)
        div %= MOD
    res = mul * mod_power(div, MOD - 2) % MOD
    return res


def prime_factorization(x):
    res = []
    i = 2
    left = x + 0
    while True:
        if (i * i > x) and (left == 1):
            break
        cnt = 0
        while left % i == 0:
            left /= i
            cnt += 1
        if cnt > 0:
            res.append(cnt)
        # print(i, res)
        i += 1
    return res


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

MOD = 10 ** 9 + 7

ans = 1
for power in prime_factorization(m):
    ans *= comb(n - 1 + power, power)
ans %= MOD

print(ans)
# print(prime_factorization(6))

Submission status: Time Limit Exceeded

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

mod=10**9+7
fuc=[1]
def fucfun(n):
    for i in range(1,n):
        e=fuc[i-1]*i
        fuc.append(e%mod)
def com(n,k):
    com=(fuc[n]%mod)*pow(fuc[k],mod-2,mod)*pow(fuc[n-k],mod-2,mod)
    return com
fucfun(m)
f=fctr(m)
s=1
for i in range(len(f)):
    t=com(f[i][1]+n-1,f[i][1])
    s=(s*t)%mod
print(s)

Submission status: Time Limit Exceeded

Solution code:
# aのp乗を求めるアルゴリズム
def modpow(a, p):
    if p == 0:
        return 1
    if p%2 == 0:
        halfp = p/2
        half = modpow(a, p/2)
        return half**2 % mod
    else:
        return a * modpow(a, p-1) % mod

def calc_comb(a, b):
    if b > a-b:
        return calc_comb(a, a-b)
    else:
        ans_mul = 1
        ans_div = 1
        for i in range(0,b):
            ans_mul *= a-i
            ans_div *= i+1
            ans_mul %= mod
            ans_div %= mod
    # ans_mul / ans_div を逆元を使って求める
    ans = ans_mul * modpow(ans_div, mod-2)
    return ans

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

m_nokori = m
ans = 1
i = 2
while i*i < m_nokori:
    if m_nokori%i == 0:
        cnt = 0
        while m_nokori%i == 0:
            cnt += 1
            m_nokori /= i
        ans *= calc_comb(n+cnt-1, n-1)
        ans %= mod
if m_nokori != 1:
    ans *= n
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

INF = float('inf')
MOD = 10 ** 9 + 7


def inpl(): return list(map(int, input().split()))


# nの素因数分解を求めるアルゴリズム
def p_factorization(n):
    tmp = []
    i = 2
    cnt = 0
    while n > 1:
        if n % i == 0:
            cnt += 1
            n //= i
        else:
            tmp.append([i, cnt])
            i += 1
            cnt = 0
    tmp.append([i, cnt])
    return tmp


# aのp乗を求めるアルゴリズム
# MOD版
# O(logp)
def pow_mod(a, p):
    if p == 0: return 1
    if p % 2 == 0:
        half_p = p // 2
        half = pow_mod(a, half_p)

        return half * half % MOD
    else:
        return a * pow_mod(a, p - 1) % MOD


# 組み合わせnCrを求めるアルゴリズム
# 逆元を使って計算
# MOD版
def cmb_mod(n, r):
    # 5C3 -> 5C2
    if r > n - r: return cmb_mod(n, n - r)
    ans_mul = 1
    ans_div = 1
    for i in range(r):
        ans_mul *= n - i
        ans_div *= i + 1
        ans_mul %= MOD
        ans_div %= MOD

    # ans_mul / ans_divをしたい
    # ans_divの逆元を使って求める
    ans = ans_mul * pow_mod(ans_div, MOD - 2) % MOD
    return ans


N, M = inpl()

fact = p_factorization(M)
ans = 1
for n, p in fact:
    ans *= cmb_mod(N - 1 + p, p)
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int, raw_input().split())
MOD = 10**9+7
 
F = [0]*100100
F[0] = 1
for i in range(1,100100):
  F[i] = i*F[i-1]%MOD
 
ans = 1
d = 2
while M>1:
  c = 0
  while M%d==0:
    M /= d
    c += 1
  if c>0:
    ans *= F[N+c-1]
    ans %= MOD
    ans *= pow(F[N-1], MOD-2, MOD)
    ans %= MOD
    ans *= pow(F[c], MOD-2, MOD)
    ans %= MOD
  d += 1

print ans

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt, ceil, factorial
from collections import Counter
m = 10**9+7

def prime_factorization(n):
    factor = []
    f = 2
    while n > 1:
        if n % f == 0:
            factor.append(f)
            n /= f
        else:
            f += 1
    return factor

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

N, M = map(int, input().split())
p = prime_factorization(M)
c = Counter(p)
ans = 1
for v in c.values():
    ans *= (comb(v + N - 1, v) % m)
print(ans%m)

Submission status: Time Limit Exceeded

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

m = 10**9+7
def is_prime(n):
    if n == 1: return False
    if n == 2: return True
    for i in range(2, ceil(sqrt(n))+1):
        if n % i == 0: return False
    return True

def prime_factorization(n):
    if is_prime(n):return [n]
    factor = []
    f = 2
    while n > 1:
        if n % f == 0:
            factor.append(f)
            n /= f
        else:
            f += 1
    return factor

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

N, M = map(int, input().split())
p = prime_factorization(M)
c = Counter(p)
ans = 1
for v in c.values():
    ans *= (comb(v + N - 1, v) % m)
print(ans%m)

Submission status: Time Limit Exceeded

Solution code:
M = 10 ** 9 + 7

def main():
    n, m = [int(s) for s in input().split()]

    print(solve(m, n))

def solve(m, n):

    fs = list(factors(m))
    table = dict()
    table[1] = dict()

    for f in fs:
        table[1][f] = 1

    h = 1
    for _ in range(1, n.bit_length()):
        row = dict()
        for f in fs:
            for g in fs:
                if f * g > m:
                    break
                row[f * g] = (row.get(f * g, 0) + table[h][f] * table[h][g]) % M
        table[h * 2] = row
        h *= 2

    prev = { 1: 1 }
    result = None
    h = 1
    for _ in range(n.bit_length()):
        if n & h:
            result = dict()
            for f in prev.keys():
                for g in table[h].keys():
                    if f * g <= m:
                        result[f * g] = (result.get(f * g, 0) + prev[f] * table[h][g]) % M
            prev = result
        h *= 2
    return result[m]

def factors(n):
    import itertools

    tail = []
    for i in itertools.count(1):
        if i * i > n:
            break

        m, r = divmod(n, i)
        if r == 0:
            yield i
            if m != i:
                tail.append(m)
    
    for i in tail[::-1]:
        yield i

main()

Submission status: Time Limit Exceeded

Solution code:
import math

n, m=map(int, input().split())
t = {}
a = int(math.sqrt(m))

s=0

line = [2, 3] + [i%2*2 + i//2 * 6 + 5 for i in range(a//3)]
while s==0:
    for i in line:
        cnt = 0
        while m%i==0:
            m=m//i
            cnt += 1

        if cnt>0:
            t[i]=cnt

        if m==1:
            s=1
            break

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

out=1
for tk in t.keys():
    out *= combi(t[tk]+n-1, n-1)
print(out%(1000000007))

Submission status: Time Limit Exceeded

Solution code:
import math
s=0
n, m=map(int, input().split())
mm = int(m)
t = {}

while s==0:
    for i in range(2,int(math.sqrt(mm))):
#         print(i)
        if m%i==0:
            m=m//i
            if m==1:
                s=1
            if i in t.keys():
                t[i]+=1
            else:
                t[i]=1
            break
out=1
def combi(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r)) 

for tk in t.keys():
    out *= combi(t[tk]+n-1, n-1)
print(out%(1000000007))

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
bigp = 10**9+7
L1 = []
L2 = []
p = 2
K = M
while K != 1:
    if K%p == 0:
        L1.append(p)
        K = K//p
        if p not in L2:
            L2.append(p)
    else:
        if p == 2:
            p += 1
        else:
            p += 2

ans = 1
def ModComb(n, r, p):
    N = n%p
    R = r%p
    if N<R:
        return 0
    if N < 2*R:
        R = N-R
    if R == 0:
        return 1
    else:
        return (n*pow(r, p-2, p))%p*ModComb(n-1, r-1, p)


for x in L2:
    primepower = L1.count(x)
    ans *= ModComb(N+primepower-1, primepower, bigp)
    ans %= bigp

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
bigp = 10**9+7
L1 = []
L2 = []
p = 2
K = M
while K != 1:
    if K%p == 0:
        L1.append(p)
        K = K//p
        if p not in L2:
            L2.append(p)
    else:
        p = p+1

ans = 1
def ModComb(n, r, p):
    N = n%p
    R = r%p
    if N<R:
        return 0
    if N < 2*R:
        R = N-R
    if R == 0:
        return 1
    else:
        return (n*pow(r, p-2, p))%p*ModComb(n-1, r-1, p)


for x in L2:
    primepower = L1.count(x)
    ans *= ModComb(N+primepower-1, primepower, bigp)%bigp

print(ans%bigp)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, M = map(int, input().split())
bigp = 10**9+7
L1 = []
L2 = []
p = 2
max = M
K = M
while p <= max:
    if K%p == 0:
        L1.append(p)
        K = K//p
        if p not in L2:
            L2.append(p)
    else:
        p = p+1

ans = 1
def ModComb(n, r, p):
    N = n%p
    R = r%p
    if N<R:
        return 0
    if N < 2*R:
        R = N-R
    if R == 0:
        return 1
    else:
        return (n*pow(r, p-2, p))%p*ModComb(n-1, r-1, p)


for x in L2:
    primepower = L1.count(x)
    ans *= ModComb(N+primepower-1, primepower, bigp)%bigp

print(ans%bigp)

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import defaultdict

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

A = defaultdict(int)
p = 10 ** 9 + 7

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

def fact(n, p=10**9 + 7):
    f = [1]
    for i in range(1, n+1):
        f.append(f[-1]*i%p)
    return f

def invfact(n, f, p=10**9 + 7):
    inv = [pow(f[n], p-2, p)]
    for i in range(n, 0, -1):
        inv.append(inv[-1]*i%p)
    return inv[::-1]

f = fact(30+10**5)
invf = invfact(30+10**5, f)

def comb(a, b):
    return f[a] * invf[b] * invf[a-b] % p

i = 2

while m != 1 and math.sqrt(m) + 1:
    while m % i == 0:
        m //= i
        A[i] += 1
    i += 1

if not A:
    print(n)
    exit()

if m != 1:
    A[m] = 1

n -= 1
ans = 1

for v in A.values():
    ans *= comb(v+n, n)
    ans %= p

print(ans)

Submission status: Time Limit Exceeded

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

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

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

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

print(x)

Submission status: Time Limit Exceeded

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

# 階上の計算
from math import factorial
from collections import defaultdict

def prime_decomposition(n):
  i = 2
  table = defaultdict(int)

  while i * i <= n:
    while n % i == 0:
      n /= i
      table[i] += 1
    i += 1

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

  return list(table.values())


def nHr(n, r):
    return factorial(n+r-1) // (factorial(r) * factorial(n-1))


mod = 10 ** 9 + 7

ans = 1

prim_d_num = prime_decomposition(M)

for p in prim_d_num:
    ans *= nHr(p+1, N-1)

print(ans % mod)