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:
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

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 power_func(a,b,p):
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p

class comb_calclator():
    def __init__(self, N, p):
        self.N = N
        self.p = p
        self.frac_N = [0 for i in range(N + 1)]
        self.frac_N[0] = 1L
        self.comb_N = {}
        for i in range(1, N + 1):
            self.frac_N[i] = (self.frac_N[i - 1] * i ) % p

    def comb(self, n, r):
        if n<0 or r<0 or n<r: return 0
        if n==0 or r==0: return 1
        if (n, r) in self.comb_N:
            return self.comb_N[(n, r)]
        a = self.frac_N[n]
        b = self.frac_N[r]
        c = self.frac_N[n - r]
        self.comb_N[(n, r)] = (a*power_func(b,self.p-2,self.p)*power_func(c,self.p-2, self.p))% self.p
        self.comb_N[(n, n - r)] = self.comb_N[(n, r)]
        return self.comb_N[(n, r)]


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] = [int(input_raw[0]), long(input_raw[1])]
    prime = prime_decomposition(M)
    prime_num = {}
    for p in prime:
        if p not in prime_num:
            prime_num[p] = 1
        else:
            prime_num[p] += 1

    cmb = comb_calclator(N * 100, 1000000007)
    count = 1L
    for p in prime_num:
        count = (count * cmb.comb(N + prime_num[p]- 1, prime_num[p])) % 1000000007

    print count
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

yd = {}
i = 2
while m != 1:
  while m % i == 0:
    if i in yd:
      yd[i] += 1
    else:
      yd[i] = 1
    m //= i
  i += 1

ans = 1
for v in yd.values():
  start = v + n - 1
  c = 1
  for _ in range(v):
    c *= start
    start -= 1
  d = 1
  for _v in range(v):
    d *= (_v + 1)
  ans *= (c // d)
print(ans % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
import math
def prime_factor(n):
    ass = []
    for i in range(2,int(n**0.5)+1):
        while n % i==0:
            ass.append(i)
            n = n//i
    if n != 1:
        ass.append(n)
    return ass
N,M = map(int,input().split())
L = prime_factor(M)
L.append(0)
K = []
cur = L[0]
cnt = 0
for i in range(len(L)):
  if cur == L[i]:
    cnt += 1
  else:
    K.append(cnt)
    cnt = 1
    cur = L[i]
ans = 1
for i in range(len(K)):
  n = K[i]+N-1
  k = N-1
  a = (math.factorial(n))%(10**9+7)
  b = (math.factorial(k)%(10**9+7))
  c = (math.factorial(n-k)%(10**9+7))
  ans *= (a*pow(b*c,10**9+5,10**9+7))%(10**9+7)
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import math
def prime_factor(n):
    ass = []
    for i in range(2,int(n**0.5)+1):
        while n % i==0:
            ass.append(i)
            n = n//i
    if n != 1:
        ass.append(n)
    return ass
N,M = map(int,input().split())
L = prime_factor(M)
L.append(0)
K = []
cur = L[0]
cnt = 0
for i in range(len(L)):
  if cur == L[i]:
    cnt += 1
  else:
    K.append(cnt)
    cnt = 1
    cur = L[i]
ans = 1
for i in range(len(K)):
  ans *= math.factorial(K[i]+N-1)//((math.factorial(N-1))*(math.factorial(K[i])))
  ans = ans%(10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
import math
a=[]
ans=1
def calc(n):#nの素因数分解
    for i in range(2,int(n**0.5)+10):
        count=0
        while n%i==0:
            n//=i
            count+=1
        if count>=1:
            a.append([i,count])
    if n!=1:
        a.append([n,1])
def conb(n,k):
    return math.factorial(n)//(math.factorial(n-k)*math.factorial(k))
calc(M)
for i in range(len(a)):
    ans*=conb(a[i][1]+N-1,a[i][1])
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import math

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

def prime_decomposition(n):
    p = 2
    prime = {}
    while n!=1:
        while n%p == 0:
            n = n//p
            if p not in prime:
                prime[p] = 0
            prime[p] += 1
        p += 1
    return prime

primes = prime_decomposition(m)
ans = 1

def combination(n,k):
    ret1 = 1
    ret2 = 1
    for i in range(k):
        ret1 *= n-i
        ret2 *= k-i
    return ret1//ret2

for pw in primes.values():
    comb = combination(pw+n-1, pw)
    ans *= comb
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

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

def prime_decomposition(n):
    p = 2
    prime = {}
    while n!=1:
        while n%p == 0:
            n = n/p
            if p not in prime:
                prime[p] = 0
            prime[p] += 1
        p += 1
    return prime

primes = prime_decomposition(m)
# print(primes)
ans = 1

def combination(n,k):
    ret1 = 1
    ret2 = 1
    for i in range(k):
        ret1 *= n-i
        ret2 *= k-i
    return ret1//ret2

for p in primes:
    comb = combination(primes[p]+n-1, primes[p])
    ans *= comb
    ans %= mod

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
# 素数リスト生成
def sieve(x):
    if x < 2: return []
    primes = [i for i in range(x)]
    primes[1] = 0
    for p in primes:
        if p > x ** (1/2): break
        if p == 0: continue
        for np in range(2 * p, x, p): primes[np] = 0
    return [p for p in primes if p != 0]

PS = sieve(10**8)

# 素因数分解
def factorint(x):
  d = {}
  for k in PS:
    if(x % k== 0):
      m = 1
      while(x % (k**m) == 0):
        m += 1
      d[k] = m - 1
      x = x / (k ** (m - 1))
      if x == 1:
        break
  return d

n, m = map(int, input().split())
f = factorint(m)
idx = [i for i in f.values()]

def fact(n):
  ret = 1
  for i in range(1, n + 1):
    ret *= i
  return ret
def com(n, r):
  if n - r < r: r = n - r
  ret = 1
  for i in range(n-r+1, n+1):
    ret *= i
  for j in range(1, r+1):
    ret //= j
  return ret

ans = 1
for i in range(len(idx)):
  ans *= com(idx[i] + n - 1, n - 1) % (10 ** 9 + 7)

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

Submission status: Time Limit Exceeded

Solution code:
# 素数リスト生成
def sieve(x):
    if x < 2: return []
    primes = [i for i in range(x)]
    primes[1] = 0
    for p in primes:
        if p > x ** (1/2): break
        if p == 0: continue
        for np in range(2 * p, x, p): primes[np] = 0
    return [p for p in primes if p != 0]

PS = sieve(10**9)

# 素因数分解
def factorint(x):
  d = {}
  for k in PS:
    if(x % k== 0):
      m = 1
      while(x % (k**m) == 0):
        m += 1
      d[k] = m - 1
      x = x / (k ** (m - 1))
      if x == 1:
        break
  return d

n, m = map(int, input().split())
f = factorint(m)
idx = [i for i in f.values()]

def fact(n):
  ret = 1
  for i in range(1, n + 1):
    ret *= i
  return ret
def com(n, r):
  if n - r < r: r = n - r
  ret = 1
  for i in range(n-r+1, n+1):
    ret *= i
  for j in range(1, r+1):
    ret //= j
  return ret

ans = 1
for i in range(len(idx)):
  ans *= com(idx[i] + n - 1, n - 1) % (10 ** 9 + 7)

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

Submission status: Time Limit Exceeded

Solution code:
def prime_facts(n: int) -> dict:
    res = {}

    if n % 2 == 0:
        res[2] = 1
        n //= 2
        while n % 2 == 0:
            res[2] += 1
            n //= 2

    if n % 3 == 0:
        res[3] = 1
        n //= 3
        while n % 3 == 0:
            res[3] += 1
            n //= 3

    k = 1
    while n > 1:
        for i in [-1, 1]:
            d = 6 * k + i
            if n % d == 0:
                res[d] = 1
                n //= d
                while n % d == 0:
                    res[d] += 1
                    n //= d
        k += 1

    return res


def factorization(N: int, M: int) -> int:
    """以下の説明において、F(N, M) はこの関数と同値。

    `a1 x a2 x ... x aN = M (式 1)`
    となる数列 {aN} の組み合わせ数を F(N, M) とする。

    まず、(式 1)より {aN} は全て M の約数であることは明らか。

    ここで、M の約数列を {dm} とする。今、aN = di とすると、
    `a1 x a2 x ... x a{N-1} = M // di`
    が成り立ち、これを満たす数列 {a{N-1}} の組み合わせ数は F(N-1, M//di) である。

    aN は任意の di を取れるので、結局、
    `F(N, M) = sigma{di} F(N-1, M//di) = sigma{di} F(N-1, M)` (式 2)
    が成り立つ。

    さらに、M を場合分けして考える。

    M = 1 のとき、(式 2)より
    `F(N, 1) = F(N-1, 1) = ... = F(1, 1) = 1` (式 3)
    が成り立つ。

    M = p (p は素数)のとき、(式 2)と(式 3)より、
    `F(N, p) = F(N-1, p) + F(N-1, 1) = F(N-1, p) + 1`
    が成り立つ。この漸化式をとけば、
    `F(N, p) = N`
    が成り立つ。

    M = p^k (p は素数)の時、めんどくさい計算の果てに
    `F(N, p^k) = PI{i=0}{k-1}(N+i) / k!`
    が成り立つ。

    M = p1...pk (pi は全て異なる素数)の時、めんどくさい計算の果てに
    `F(N,p1...pk) = N^k`

    M = p1^k1 ... pm^km (pi は全て異なる素数)の時、めんどくさい計算の果てに
    `F(N,p1^k1...pm^km) = F(N,p1^k1)...F(N,pm^km)`
    が成り立つ。
    """
    pi = [1] * 101
    fact = [1] * 101
    for i in range(1, 101):
        pi[i] = (N+i-1) * pi[i-1]
        fact[i] = i * fact[i-1]
    primes = prime_facts(M)
    ret = 1
    for k in primes.values():
        ret *= pi[k] // fact[k]

    return ret % 1000000007


if __name__ == "__main__":
    N, M = map(int, input().split())
    ans = factorization(N, M)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def prime_facts(n: int) -> dict:
    res = {}
    d = 2
    while n > 1:
        if n % d == 0:
            res[d] = 1
            n //= d

        while n % d == 0:
            res[d] += 1
            n //= d

        if d == 2:
            d += 1
        else:
            d += 2

    return res


def pi(start: int, stop: int, n: int) -> int:
    """(N+start)x...x(N+stop) を計算する。
    """
    res = 1
    for i in range(start, stop+1):
        res *= (n + i)
    return res


def fact(n: int) -> int:
    """n!を計算する。
    """
    res = 1
    for i in range(n):
        res *= (i + 1)
    return res


def factorization(N: int, M: int) -> int:
    """以下の説明において、F(N, M) はこの関数と同値。

    `a1 x a2 x ... x aN = M (式 1)`
    となる数列 {aN} の組み合わせ数を F(N, M) とする。

    まず、(式 1)より {aN} は全て M の約数であることは明らか。

    ここで、M の約数列を {dm} とする。今、aN = di とすると、
    `a1 x a2 x ... x a{N-1} = M // di`
    が成り立ち、これを満たす数列 {a{N-1}} の組み合わせ数は F(N-1, M//di) である。

    aN は任意の di を取れるので、結局、
    `F(N, M) = sigma{di} F(N-1, M//di) = sigma{di} F(N-1, M)` (式 2)
    が成り立つ。

    さらに、M を場合分けして考える。

    M = 1 のとき、(式 2)より
    `F(N, 1) = F(N-1, 1) = ... = F(1, 1) = 1` (式 3)
    が成り立つ。

    M = p (p は素数)のとき、(式 2)と(式 3)より、
    `F(N, p) = F(N-1, p) + F(N-1, 1) = F(N-1, p) + 1`
    が成り立つ。この漸化式をとけば、
    `F(N, p) = N`
    が成り立つ。

    M = p^k (p は素数)の時、めんどくさい計算の果てに
    `F(N, p^k) = PI{i=0}{k-1}(N+i) / k!`
    が成り立つ。

    M = p1...pk (pi は全て異なる素数)の時、めんどくさい計算の果てに
    `F(N,p1...pk) = N^k`

    M = p1^k1 ... pm^km (pi は全て異なる素数)の時、めんどくさい計算の果てに
    `F(N,p1^k1...pm^km) = F(N,p1^k1)...F(N,pm^km)`
    が成り立つ。
    """
    pi = [1] * 101
    fact = [1] * 101
    for i in range(1, 101):
        pi[i] = (N+i-1) * pi[i-1]
        fact[i] = i * fact[i-1]
    primes = prime_facts(M)
    ret = 1
    for k in primes.values():
        ret *= pi[k] // fact[k]

    return ret % 1000000007


if __name__ == "__main__":
    N, M = map(int, input().split())
    ans = factorization(N, M)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def prime_facts(n: int) -> dict:
    res = {}
    d = 2
    while n > 1:
        if n % d == 0:
            res[d] = 1
            n //= d

        while n % d == 0:
            res[d] += 1
            n //= d

        if d == 2:
            d += 1
        else:
            d += 2

    return res


def pi(start: int, stop: int, n: int) -> int:
    """(N+start)x...x(N+stop) を計算する。
    """
    res = 1
    for i in range(start, stop+1):
        res *= (n + i)
    return res


def fact(n: int) -> int:
    """n!を計算する。
    """
    res = 1
    for i in range(n):
        res *= (i + 1)
    return res


def factorization(N: int, M: int) -> int:
    """以下の説明において、F(N, M) はこの関数と同値。

    `a1 x a2 x ... x aN = M (式 1)`
    となる数列 {aN} の組み合わせ数を F(N, M) とする。

    まず、(式 1)より {aN} は全て M の約数であることは明らか。

    ここで、M の約数列を {dm} とする。今、aN = di とすると、
    `a1 x a2 x ... x a{N-1} = M // di`
    が成り立ち、これを満たす数列 {a{N-1}} の組み合わせ数は F(N-1, M//di) である。

    aN は任意の di を取れるので、結局、
    `F(N, M) = sigma{di} F(N-1, M//di) = sigma{di} F(N-1, M)` (式 2)
    が成り立つ。

    さらに、M を場合分けして考える。

    M = 1 のとき、(式 2)より
    `F(N, 1) = F(N-1, 1) = ... = F(1, 1) = 1` (式 3)
    が成り立つ。

    M = p (p は素数)のとき、(式 2)と(式 3)より、
    `F(N, p) = F(N-1, p) + F(N-1, 1) = F(N-1, p) + 1`
    が成り立つ。この漸化式をとけば、
    `F(N, p) = N`
    が成り立つ。

    M = p^k (p は素数)の時、めんどくさい計算の果てに
    `F(N, p^k) = PI{i=0}{k-1}(N+i) / k!`
    が成り立つ。

    M = p1...pk (pi は全て異なる素数)の時、めんどくさい計算の果てに
    `F(N,p1...pk) = N^k`

    M = p1^k1 ... pm^km (pi は全て異なる素数)の時、めんどくさい計算の果てに
    `F(N,p1^k1...pm^km) = F(N,p1^k1)...F(N,pm^km)`
    が成り立つ。
    """
    primes = prime_facts(M)
    ret = 1
    for k in primes.values():
        ret *= pi(0, k - 1, N) // fact(k)

    return ret % 1000000007


if __name__ == "__main__":
    N, M = map(int, input().split())
    ans = factorization(N, M)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

def prime_division(n):
    ans = []
    m = int(n ** 0.5)
    i = 2
    while i <= m:
        if n % i == 0:
            cnt = 0
            while n % i == 0:
                n //= i
                cnt += 1
            ans.append((i, cnt))
            m = int(n ** 0.5)
        i += 1
    if n != 1:
        ans.append((n, 1))
    return ans

#  aabaaba  count+(N-1) C (N-1)

N,M=map(int,input().split())
pms=prime_division(M)
ans = 1
for pm in pms:
    #print(pm)
    ans *= math.factorial(pm[1]+(N-1)) // (math.factorial(pm[1]) * math.factorial(N-1))

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import math
n,m = map(int, input().split())
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def prime_decomposition(n, table):
    i = 2
    while i * i <= n:
        while n % i == 0:
            n /= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
table = []
prime_decomposition(m, table)
c = Counter(table).values()
cc = Counter(c)
ans = 1
N = n-1
for i,j in cc.items():
  ans *= ((combinations_count(N+i,i))**j)%(10**9+7)
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import math
n,m = map(int, input().split())
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def prime_decomposition(n, table):
    N = n**(1/2)
    i = 2
    while i <= N:
        while n % i == 0:
            n /= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
table = []
prime_decomposition(m, table)
c = Counter(table).values()
cc = Counter(c)
ans = 1
N = n-1
for i,j in cc.items():
  ans *= (combinations_count(N+i,i))**j
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import math
n,m = map(int, input().split())
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def prime_decomposition(n, table):
    i = 2
    while i * i <= n:
        while n % i == 0:
            n /= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
table = []
prime_decomposition(m, table)
c = Counter(table).values()
cc = Counter(c)
ans = 1
N = n-1
for i,j in cc.items():
  ans *= (combinations_count(N+i,i))**j
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

def comb(n, r):
    return factorial(n) // factorial(r) // factorial(n - r)

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

c = []
i = 2
mt = m

while i * i <= mt:
    ci = 0
    while mt % i == 0:
        mt = mt // i
        ci += 1
    if ci > 0:
        c.append(ci)
    i += 1
if mt > 1:
    c.append(1)
    
p = 1
for j in range(0, len(c)):
    p *= comb(n - 1 + c[j], c[j])

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

Submission status: Time Limit Exceeded

Solution code:
import math
def comb(x,y):
    f = 1
    for i in range(y):
        f *= (x-i)
        f //= (i+1)

    return f

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

cnt = [0]
for i in range(2,m+1):
    while m!=i:
        if m%i==0:
            m //=i
            cnt[-1]+=1
        else:
            cnt.append(0)
            break
    if m==i:
        cnt[-1]+=1
        break
cnt = [item for item in cnt if cnt != 0]


res = 1
r = 10**9 +7
for item in cnt:
    res = (res* comb(item+n-1,item))%r

print(res%r)

Submission status: Time Limit Exceeded

Solution code:
import math
def comb(x,y):
    f = 1
    for i in range(y):
        f *= (x-i)
        f //= (i+1)

    return f

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

cnt = [0]
for i in range(2,m+1):
    while m!=i:
        if m%i==0:
            m //=i
            cnt[-1]+=1
        else:
            cnt.append(0)
            break
    if m==i:
        cnt[-1]+=1
        break
cnt = [item for item in cnt if cnt != 0]


res = 1

for item in cnt:
    res *= comb(item+n-1,item)

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

Submission status: Time Limit Exceeded

Solution code:
import math
def comb(x,y):
    f = 1
    for i in range(y):
        f *= (x-i)
        f //= (i+1)

    return f

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

cnt = [0]
for i in range(2,m+1):
    while m!=i:
        if m%i==0:
            m //=i
            cnt[-1]+=1
        else:
            cnt.append(0)
            break
    if m==i:
        cnt[-1]+=1
        break
cnt = [item for item in cnt if cnt != 0]


res = 1

for item in cnt:
    res *= comb(item+n-1,n-1)

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

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc110/tasks/abc110_d

def get_prime_dic(n):
    dic = {}

    while n % 2 == 0:
        if 2 in dic:
            dic[2] += 1
        else:
            dic[2] = 1
        n = n // 2

    i = 3
    while i <= n:
        while n % i == 0:
            n //= i
            if i in dic:
                dic[i] += 1
            else:
                dic[i] = 1
        i += 2
    if n > 1:
        dic[n] = 1
    return dic


# Calculate count of combination
def combination(n, r):
    a = 1
    b = 1
    for i in range(r):
        a *= (n - i)
        b *= (i + 1)
    return a // b


def main():
    N, M = map(int, input().split())
    d = get_prime_dic(M)
    # print(d)

    ans = 1
    for k, v in d.items():
        ans *= combination(v + N - 1, v)
        ans %= 1000000007

    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc110/tasks/abc110_d

def get_prime_dic(n):
    dic = {}

    while n % 2 == 0:
        if 2 in dic:
            dic[2] += 1
        else:
            dic[2] = 1
        n = n // 2

    i = 3
    while i <= n:
        while n % i == 0:
            n //= i
            if i in dic:
                dic[i] += 1
            else:
                dic[i] = 1
        i += 2
    return dic


# Calculate count of combination
def combination(n, r):
    a = 1
    b = 1
    for i in range(r):
        a *= (n - i)
        b *= (i + 1)
    return a // b


def main():
    N, M = map(int, input().split())
    d = get_prime_dic(M)
    # print(d)

    ans = 1
    for k, v in d.items():
        ans *= combination(v + N - 1, v)
        ans %= 1000000007

    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc110/tasks/abc110_d


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


def get_prime_dic(n):
    dic = {}

    i = 2
    while i <= n:
        while n % i == 0:
            n //= i
            if i in dic:
                dic[i] += 1
            else:
                dic[i] = 1
        i += 1
    return dic


# Calculate count of combination
def combination(n, r):
    a = 1
    b = 1
    for i in range(r):
        a *= (n - i)
        b *= (i + 1)
    return a // b


def main():

    d = get_prime_dic(M)
    # print(d)

    ans = 1

    for k, v in d.items():
        ans *= combination(v + N - 1, v)
        ans %= 1000000007


    print(ans)

main()

Submission status: Time Limit Exceeded

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


def get_prime_dic(n):
    dic = {}

    i = 2
    while i <= n:
        while n % i == 0:
            n //= i
            if i in dic:
                dic[i] += 1
            else:
                dic[i] = 1
        i += 1
    return dic


# Calculate count of combination
def combination(n, r):
    a = 1
    b = 1
    for i in range(r):
        a *= (n - i)
        b *= (i + 1)
    return a // b

d = get_prime_dic(M)
# print(d)

ans = 1

for k, v in d.items():
    ans *= combination(v + N - 1, v)
    ans %= 1000000007


print(ans)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc110/tasks/abc110_d


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


def get_prime_dic(n):
    dic = {}

    i = 2
    while i <= n:
        while n % i == 0:
            n //= i
            if i in dic:
                dic[i] += 1
            else:
                dic[i] = 1
        i += 1
    return dic


# Calculate count of combination
def combinations_count(n, r):
    import math
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


d = get_prime_dic(M)
# print(d)

ans = 1

for k, v in d.items():
    ans *= combinations_count(v + N - 1, v)


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

Submission status: Time Limit Exceeded

Solution code:
# 2 6=>4 (1,6)*2,(2,3)*2
# 3 12=>18 (1,1,12)*3,(1,2,6)*6,(1,3,4)*6,(2,2,3)*3
import math
def comb(a,b): # aCb
    return math.factorial(a)//math.factorial(a-b)//math.factorial(b)

n,m=map(int,input().split())
divisor={}
tmp=m
# for i in range(2,m+1):
i=2
while i*i<=m:
    while tmp%i==0:
        tmp//=i
        divisor.setdefault(i,0)
        divisor[i]+=1
    # if tmp==1:
    #     break
    i+=1
if tmp>1:
    divisor[tmp]=1
# print(divisor)
cnt=1
for key in divisor:
    c=divisor[key]
    cnt*=comb(c+n-1,c)
print(cnt%1000000007)

Submission status: Time Limit Exceeded

Solution code:
# 2 6=>4 (1,6)*2,(2,3)*2
# 3 12=>18 (1,1,12)*3,(1,2,6)*6,(1,3,4)*6,(2,2,3)*3
import math
def comb(a,b): # aCb
    return math.factorial(a)//math.factorial(a-b)//math.factorial(b)

n,m=map(int,input().split())
divisor={}
tmp=m
for i in range(2,m+1):
    while tmp%i==0:
        tmp//=i
        divisor.setdefault(i,0)
        divisor[i]+=1
    if tmp==1:
        break
# print(divisor)
cnt=1
for key in divisor:
    c=divisor[key]
    cnt*=comb(c+n-1,c)
print(cnt%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import math
mod = 1000000007
N,M = list(map(int,input().strip().split()))
m_sqrt = int(math.sqrt(M))
def P(n, r):
  return math.factorial(n)//math.factorial(n-r)
def C(n, r):
  return P(n, r)//math.factorial(r)

ans = 1
cnt = 0
while  M%2 == 0:
  M = M//2
  cnt += 1
ans *= C(N+cnt-1,cnt)
cnt = 0

for i in range(3,m_sqrt+1,2):
  while M%i == 0:
    M = M//i
    cnt += 1
  if cnt != 0:
    ans *= C(N+cnt-1,cnt)
    cnt = 0
if M != 1:
    ans *= C(N,1)

print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import math
import collections
mod = 1000000007
N,M = list(map(int,input().strip().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 P(n, r):
  return math.factorial(n)//math.factorial(n-r)

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


l = list(collections.Counter(prime_decomposition(M)).values())


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

Submission status: Time Limit Exceeded

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

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

cnt = 0
while  M%2 == 0:
  M = M//2
  cnt += 1
l.append(cnt)
  
i = 3
while M != 1:
  cnt = 0
  while M%i == 0:
    M = M//i
    cnt += 1
  if cnt != 0:
    l.append(cnt)
  i += 2
  
ans = 1
for i in l:
  ans *= C(N+i-1,i)
  
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import math

def isprime(n):
    if(n<2):
        return False
    for i in range(2,int(n**0.5)+1):
        if(n%i==0):
            return False
    return True

def primelist(n):
    return [i for i in range(n) if isprime(i)]

def factor(n):
    f = {}
    for p in primelist(int(n**0.5)+1):
        while(n % p == 0):
            f[p] = f.get(p, 0) + 1
            n //= p
    if(n != 1):
        f[n] = 1
    return f

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

MOD = 1000000007

mod_fact_dict = {}

def mod_fact(n):
    res = 1
    while n > 0:
        res *= n
        res %= MOD
        n -= 1
    return res

def duplicate_combination(n, k):
    t = n + k - 1
    if t not in mod_fact_dict:
        mod_fact_dict[t] = mod_fact(t)
    res = mod_fact_dict[t]
    res %= MOD
    if n not in mod_fact_dict:
        mod_fact_dict[n] = mod_fact(n)
    res *= mod_inv(mod_fact_dict[n])
    res %= MOD
    t = k - 1
    if t not in mod_fact_dict:
        mod_fact_dict[t] = mod_fact(t)
    res *= mod_inv(mod_fact_dict[t])
    res %= MOD
    return res

def _mod_inv(x, n):
    if n == 0:
        return 1
    t = _mod_inv(x, n >> 1)
    t = (t * t) % MOD
    return (t * (x if n & 1 else 1)) % MOD

def mod_inv(n):
    return _mod_inv(n, MOD - 2)

def primes(x):
    n = x
    for i in range(2, n + 1):
        if x == 1:
            return
        while x % i == 0:
            x //= i
            counter[i] += 1

if __name__ == '__main__':
    n, m = map(int, input().split())

    counter = defaultdict(int)
    primes(m)
    ans = 1
    d = {}
    for x in counter.values():
        if x not in d:
            d[x] = duplicate_combination(x, n)
        ans *= d[x]
        ans %= MOD
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

MOD = 1000000007

def mod_fact(n):
    res = 1
    while n > 0:
        res *= n
        res %= MOD
        n -= 1
    return res

def duplicate_combination(n, k):
    res = mod_fact(n + k - 1)
    res %= MOD
    res *= mod_inv(mod_fact(n))
    res %= MOD
    res *= mod_inv(mod_fact(k - 1))
    res %= MOD
    return res

def _mod_inv(x, n):
    if n == 0:
        return 1
    t = _mod_inv(x, n >> 1)
    t = (t * t) % MOD
    return (t * (x if n & 1 else 1)) % MOD

def mod_inv(n):
    return _mod_inv(n, MOD - 2)

def primes(x):
    n = x
    for i in range(2, n + 1):
        if x == 1:
            return
        while x % i == 0:
            x //= i
            counter[i] += 1

if __name__ == '__main__':
    n, m = map(int, input().split())

    counter = defaultdict(int)
    primes(m)
    ans = 1
    d = {}
    for x in counter.values():
        if x not in d:
            d[x] = duplicate_combination(x, n)
        ans *= d[x]
        ans %= MOD
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

MOD = 1000000007

def mod_fact(n):
    res = 1
    while n > 0:
        res *= n
        res %= MOD
        n -= 1
    return res

def duplicate_combination(n, k):
    res = mod_fact(n + k - 1)
    res %= MOD
    res *= mod_inv(mod_fact(n))
    res %= MOD
    res *= mod_inv(mod_fact(k - 1))
    res %= MOD
    return res

def _mod_inv(x, n):
    if n == 0:
        return 1
    t = _mod_inv(x, n >> 1)
    t = (t * t) % MOD
    return (t * (x if n & 1 else 1)) % MOD

def mod_inv(n):
    return _mod_inv(n, MOD - 2)

def primes(x):
    n = x
    for i in range(2, n + 1):
        if x == 1:
            return
        while x % i == 0:
            x //= i
            counter[i] += 1

if __name__ == '__main__':
    n, m = map(int, input().split())

    counter = defaultdict(int)
    primes(m)
    ans = 1
    for x in counter.values():
        ans *= duplicate_combination(x, n)
        ans %= MOD
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from scipy.misc import comb
n,m=map(int,input().split())
a=1
p=2
while m>1:
    if m%p:
        p+=1
        continue
    c=0
    while not m%p:
        m//=p
        c+=1
    a=a*comb(n+c-1,c,exact=1)%(10**9+7)
print(a)