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: Wrong Answer

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

# 素因数分解
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: Wrong Answer

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**6)

# 素因数分解
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: Wrong Answer

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

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

table = prime_decomposition(m)
b = []
for i in set(table):
    b.append(table.count(i))
ans = 1
import itertools
for b_ in b:
    n_ = b_+n-1
    comb = 1
    for i in range(b_):
        comb *= n_-i
        comb /= i+1
    ans *= comb
print(int(ans%(1e9+7)))

Submission status: Wrong Answer

Solution code:
from math import sqrt


def prime_facts(n: int) -> dict:
    res = {}
    d = 2
    while d * d <= n:
        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 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 と fact の初期化
    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: Wrong Answer

Solution code:
from math import sqrt


def prime_facts(n: int) -> dict:
    res = {}
    lim = int(sqrt(n)) + 1

    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:
        finish = False
        for i in [-1, 1]:
            d = 6 * k + i
            if lim < d:
                finish = True
                break

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

        if finish:
            break
        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 と fact の初期化
    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: Wrong Answer

Solution code:
from math import sqrt


def prime_facts(n: int) -> dict:
    res = {}
    lim = int(sqrt(n)) + 1

    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:
        finish = False
        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

            if lim < d:
                finish = True
        if finish:
            break
        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: Wrong Answer

Solution code:
from math import sqrt


def prime_facts(n: int) -> dict:
    res = {}
    lim = int(sqrt(n)) + 1

    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:
        finish = False
        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

            if lim <= d:
                finish = True
        if finish:
            break
        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: Wrong Answer

Solution code:
from math import sqrt


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
    lim = int(sqrt(n)) + 1
    while n > 1:
        finish = False
        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

            if lim <= d:
                finish = True
        if finish:
            break
        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: Wrong Answer

Solution code:
MOD = 10**9 + 7

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

C = [[0 for i in range(40)] for j in range(n+40)]

def genprime(nnn):
    prime = [2,3]
    for i in range(5,nnn):
        f = True
        for p in prime:
            if(p*p > i):break
            if i % p == 0 :
                f = False
                break
        if f :prime.append(i)
    return prime

C[1][0],C[1][1] = 1,1
for i in range(2,n+40):
    for j in range(min((i+1),40)):
        if(i == j):
            C[i][i] = 1
            continue
        if(j == 0):
            C[i][j] = 1
            continue
        C[i][j] = (C[i-1][j-1]+C[i-1][j]) % MOD

prime = genprime(100000)

cnt = [0 for i in range(len(prime))]

for k,pp in enumerate(prime):
    if(m == 1):break
    while(m % pp == 0):
        m //= pp
        cnt[k] += 1
ans = 1
for k,pp in enumerate(cnt):
    if pp == 0:continue
    ans = (ans *C[pp+n-1][pp]) % MOD

print(ans)

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7

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

C = [[0 for i in range(31)] for j in range(n+40)]

def genprime(nnn):
    prime = [2,3]
    for i in range(5,nnn):
        f = True
        for p in prime:
            if(p*p > i):break
            if i % p == 0 :
                f = False
                break
        if f :prime.append(i)
    return prime

C[1][0],C[1][1] = 1,1
for i in range(2,n+40):
    for j in range(min((i+1),31)):
        if(i == j):
            C[i][i] = 1
            continue
        if(j == 0):
            C[i][j] = 1
            continue
        C[i][j] = (C[i-1][j-1]+C[i-1][j]) % MOD

prime = genprime(100000)

cnt = [0 for i in range(len(prime))]

for k,pp in enumerate(prime):
    if(m == 1):break
    while(m % pp == 0):
        m //= pp
        cnt[k] += 1
ans = 1
for k,pp in enumerate(cnt):
    if pp == 0:continue
    ans = (ans *C[pp+n-1][pp]) % MOD

print(ans)

Submission status: Wrong Answer

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

def fact(m):
    c = Counter()
    s = 2
    while s**2 <= m:
        if m % s:
            s += 1
            continue
        while m % s == 0:
            c[s] += 1
            m //= s
    if m > 1:
        c[m] += 1
    return c

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

ans = 1
for cnt in fact(m).values():
    print(cnt)
    ans = ans*comb(cnt+n-1, cnt) % mod
#    for i in range(cnt):
#        ans = ans*(cnt+n-1-i)//(i+1)
print(ans % mod)

Submission status: Wrong Answer

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,min([i,N])))**j)%(10**9+7)
print(ans)

Submission status: Wrong Answer

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)

Submission status: Wrong Answer

Solution code:
def gen_to_list(func):
    def wrapper(*args):
        return list(func(*args))
    return wrapper
def memorize(func):
    memo = {}
    def wrapper(*args):
        if args not in memo:
            memo[args] = func(*args)
        return memo[args]
    return wrapper
@gen_to_list
def factorize(n, factor=2, index=0):
    counter = 0
    while True:
        if n%factor==0:
            n //=factor
            counter += 1
        else:
            break
    if counter>0:
        yield (factor, counter)
    if factor**2 < n:
        yield from factorize(n, factor+1)
    elif n>2:
        yield (n, 1)
@memorize
def choose(N, M):
    if M>N:
        return 0
    if N==0 or M==0:
        return 1
    else:
        return N*choose(N-1, M-1)//M
def ans(N, M):
    val = 1
    for _, r in factorize(M):
        val *= choose(N+r-1, r)
        val %= (10**9+7)
    return val
print(*map(int, input().split()))

Submission status: Wrong Answer

Solution code:
def gen_to_list(func):
    def wrapper(*args):
        return list(func(*args))
    return wrapper
def memorize(func):
    memo = {}
    def wrapper(*args):
        if args not in memo:
            memo[args] = func(*args)
        return memo[args]
    return wrapper
@gen_to_list
def factorize(n, factor=2, index=0):
    counter = 0
    while True:
        if n%factor==0:
            n //=factor
            counter += 1
        else:
            break
    if counter>0:
        yield (factor, counter)
    if factor**2 < n:
        yield from factorize(n, factor+1)
    elif n>2:
        yield (n, 1)
@memorize
def choose(N, M, m):
    if M>N:
        return 0
    if N==0 or M==0:
        return 1
    else:
        return N*choose(N-1, M-1, m)//M
def ans(N, M):
    val = 1
    for _, r in factorize(M):
        val *= choose(N+r-1, r, 10**9+7)
        val %= (10**9+7)
    return val
print(*map(int, input().split()))

Submission status: Wrong Answer

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,int(math.sqrt(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: Wrong Answer

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

factors = []
for i in range(int(math.sqrt(m)),0,-1):
    if m%i == 0:
        factors.insert(0,i)
        factors.append(m//i)

accum = []

for i in range(len(factors)):
    tmp = []
    for j in range(i - 1,-1,-1):
        if factors[i]%factors[j] == 0:
            tmp.append(j)
    accum.append(tmp)

dp = [1]*len(factors)
x = 10**9 + 7
for i in range(1,n):
    for j in range(len(factors)-1,0,-1):
        for idx in accum[j]:
            dp[j] = (dp[j] + dp[idx])%x

print(dp[-1] %(10**9+7))

Submission status: Wrong Answer

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 combinations_count(n, r):
    import math
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


def combination(n, r):
    ret = 1
    a = 1
    b = 1
    for i in range(1,r+1):
        a *= (n+i-1)
        b *= (r-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: Wrong Answer

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 * 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: Wrong Answer

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: Wrong Answer

Solution code:
def cmb(n,r):
    r=min(r,n-r)
    result=1
    for i in range(n-r+1,n+1):
        result*=i
    for i in range(1,r+1):
        result//=i
    return result


N,M = map(int,input().split())
l = {}
t = M**0.5//1+1
t = int(t+1)
for i in range(2,t):
    while M%i==0:
        l[i] = l.get(i,0)+1
        M/=i
r = 1
for i,j in l.items():
    r *= cmb(j+N-1,j)%(10**9+7)
    r %= (10**9+7)
print(r)

Submission status: Wrong Answer

Solution code:
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


N,M = map(int,input().split())
l = {}
t = M**0.5//1+1
t = int(t+1)
for i in range(2,t):
    while M%i==0:
        l[i] = l.get(i,0)+1
        M/=i
r = 1
for i,j in l.items():
    r *= cmb(j+N-1,j)%(10**9+7)
    r %= (10**9+7)
print(r)

Submission status: Wrong Answer

Solution code:
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


N,M = map(int,input().split())
l = {}
t = M**0.5//1+1
t = int(t+1)
for i in range(2,t):
    while M%i==0:
        l[i] = l.get(i,0)+1
        M/=i
r = 1
for i,j in l.items():
    r *= cmb(j+N-1,j)
print(r%(10**9+7))

Submission status: Wrong Answer

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
# N,M = map(int, input().split())
from collections import defaultdict
import math

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

for i in range(2,10**5):
    s = 0
    while m%i == 0 and m > 1:
        m = m //i
        s += 1
    if s>0:
        primelist[i] = s

if m>1:
    primelist[10**9] = 1

def comb(n,k):
    res = 1
    for i in range(1,1+k):
        res = res * (n-i+1)
        res %= MOD
        res *= pow(i, MOD-2, MOD)
    return res
ans = 1
print(primelist.items())
for l,t in primelist.items(): # for defaultdict
    ans *= comb(N-1+t, t)
    ans %= MOD
print(ans)

Submission status: Wrong Answer

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
# N,M = map(int, input().split())
from collections import defaultdict
import math

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

for i in range(2,10**5):
    s = 0
    while m%i == 0 and m > 1:
        m = m //i
        s += 1
    if s>0:
        primelist[i] = s
def comb(n,k):
    res = 1
    for i in range(1,1+k):
        res = res * (n-i+1)
        res %= MOD
        res *= pow(i, MOD-2, MOD)
    return res
ans = 1
for l,t in primelist.items(): # for defaultdict
    ans *= comb(N-1+t, t)
    ans %= MOD
print(ans)

Submission status: Wrong Answer

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

def is_prime_2(num):
    if num < 2:
        return False
    if num % 2 == 0:
        l.append(2)
        return is_prime_2(num//2)
    if num % 3 == 0:
        l.append(3)
        return is_prime_2(num//3)
    if num % 5 == 0:
        l.append(5)
        return is_prime_2(num//5)
        
    prime = 7
    step = 4
    num_sqrt = math.sqrt(num)
    while prime <= num_sqrt:
        if num % prime == 0:
            l.append(prime)
            return is_prime_2(num//prime)
        prime += step
        step = 6 - step
    return True

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

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

is_prime_2(M)

pl = list(collections.Counter(l).values())

ans = 1
for i in pl:
  ans *= C(N+i-1,i)

print(ans%mod)

Submission status: Wrong Answer

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)


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

Submission status: Wrong Answer

Solution code:
import scipy.misc
import math

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

M = m
lst, count = [],[]
for i in range(2,int(math.sqrt(m))+1):
    while M % i == 0:
        M = M // i
        if i not in lst:
            count.append(1)
            lst.append(i)
        else:
            count[-1] += 1
if M > 1:
    lst.append(M)
    count.append(1)       

ans = 1
for i in count:
    ans = ans * scipy.misc.comb(i+n-1,i)
    ans = ans % (10**9+7) 

print(int(ans))

Submission status: Wrong Answer

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(f)
print(ans)

Submission status: Wrong Answer

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


def combination(n, r):
    r = min(r, n - r)
    result = 1
    for i in range(n - r + 1, n + 1):
        result *= i
    for i in range(1, r + 1):
        result //= i
    return result


def factorize(x):
    i = 2
    result = {}
    while True:
        if i**2 > x:
            break
        count = 0
        while x % i == 0:
            x //= i
            count += 1
        if count != 0:
            result[i] = count
        i += 1
    if x > 1:
        result[x] = 1
    return result


ans = 1
mod = 10**9 + 7
result = factorize(M)
for e in result.values():
    comb = combination(e + N - 1, e) % mod
    ans = ans * comb % mod

if len(result) != 0:
    print(ans)
else:
    print(0)

Submission status: Wrong Answer

Solution code:
import math
def fctr(n):
    f = []
    c = 0
    for i in range(2,int(n**0.5)+1):
        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
def c_count(n,r):
    return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))


mod = 10**9 + 7
N,M = list(map(int,input().split()))
ans = 0
s = fctr(M)

for i in s:
    if ans == 0:
        ans = c_count(N-1+i[1],i[1]) % mod
    else:
        ans = (ans*c_count(N-1+i[1],i[1]))%mod
        
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
MOD = 1000000007
def comb(x, y):
    ret = 1
    for a in range(x, x - y, -1):
        ret *= a
    for b in range(y, 0, -1):
        ret //= b
    return ret

ans = 1
for i in range(2, 100000):
    if i > m:break
    cnt = 0
    while m % i == 0:
        cnt += 1
        m //= i
    ans *= comb(cnt + n - 1, cnt)
if i != 1:
    ans *= comb(n, 1)

print(ans % MOD)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
MOD = 1000000007
def comb(x, y):
    ret = 1
    for a in range(x, x - y, -1):
        ret *= a
    for b in range(y, 0, -1):
        ret //= b
    return ret

ans = 1
for i in range(2, 100000):
    if i > m:break
    cnt = 0
    while m % i == 0:
        cnt += 1
        m //= i
    ans *= comb(cnt + n - 1, cnt)

print(ans % MOD)

Submission status: Wrong Answer

Solution code:
n,m=[int(x) for x in input().split()]
from collections import defaultdict
ans=1
from math import sqrt,factorial
def indexer(num,base):
    index=0
    while num%(base**index)==0:
        index+=1
    return index-1
def ncm(a,b):
    result=1
    for i in range(b):
        result*=(a-i)
        result=result//(i+1)
    return result
for i in range(2,int(sqrt(m))+5):
    index=indexer(m,i)
    m=m//(i**index)
    if index>0:
        ans*=ncm(n-1+index,index)
print(ans%(10**9+7))

Submission status: Wrong Answer

Solution code:
n,m=[int(x) for x in input().split()]
from collections import defaultdict
ans=1
from math import sqrt,factorial
def indexer(num,base):
    index=0
    while num%(base**index)==0:
        index+=1
    return index-1
def ncm(a,b):
    result=1
    for i in range(b):
        result*=(a-i)
        result=result//(i+1)
    return result
for i in range(2,int(sqrt(m))+5):
    index=indexer(m,i)
    m=m//(i**index)
    if index!=0:
        ans*=ncm(n-1+index,index)
print(ans%(10**9+7))

Submission status: Wrong Answer

Solution code:
n,m=[int(x) for x in input().split()]
from collections import defaultdict
ans=1
from math import sqrt,factorial
def indexer(num,base):
    index=0
    while num%(base**index)==0:
        index+=1
    return index-1
def ncm(a,b):
    result=1
    for i in range(b):
        result*=(a-i)
        result=result//(i+1)
    return result
for i in range(2,int(sqrt(m))+2):
    index=indexer(m,i)
    m=m//(i**index)
    if index!=0:
        ans*=ncm(n-1+index,index)
print(ans%(10**9+7))