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:
N, M = map(int, input().split())
mod = int(1e+9 + 7)
a = mod - 2
ax = []
while a != 0:
  ax = [a%2] + ax[:]
  a //= 2
def inved(x):
  y = 1
  for i in range(len(ax)):
    if ax[i] == 1:
      y *= x
      y %= mod
    if i != len(ax) - 1:
      y *= y
      y %= mod
  return y

p, n = 2, M
L = []
dig = 1
while n != 1:
  i = 0
  while n % p == 0:
    n //= p
    dig *= p
    i += 1
  if i != 0:
    L.append([p, i])
  p += 1
  if p > int(M**(1/2)) and dig != M:
    if L != []:
      L.append([M//dig, 1])
    else:
      L.append([M, 1])
    break
print(L)
if M == 1:
  print(1)
else:
  prod = 1
  mm = max(x[1] for x in L)
  fact = [1]
  for i in range(N + mm - 1):
    fact.append((fact[i] * (i + 1)) % mod)
  invf = inved(fact[N - 1])
  for i in L:
    pad = (fact[N - 1 + i[1]] * inved(fact[i[1]]) * invf) % mod
    prod *= pad
    prod %= mod
  print(prod)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
mod = int(1e+9 + 7)
a = mod - 2
ax = []
while a != 0:
  ax = [a%2] + ax[:]
  a //= 2
def inved(x):
  y = 1
  for i in range(len(ax)):
    if ax[i] == 1:
      y *= x
      y %= mod
    if i != len(ax) - 1:
      y *= y
      y %= mod
  return y

p, n = 2, M
L = []
dig = 1
while n != 1:
  i = 0
  while n % p == 0:
    n //= p
    dig *= p
    i += 1
  if i != 0:
    L.append([p, i])
  p += 1
  if p > int(M**(1/2)) and dig != M:
    if L != []:
      L1 = L[:]
      for x in L1:
        t = 1
        for y in range(x[1]):
          t *= x[0]
        if M > t * t:
          L.append([M//t, 1])
    else:
      L.append([M, 1])
    break

if M == 1:
  print(1)
else:
  prod = 1
  mm = max(x[1] for x in L)
  fact = [1]
  for i in range(N + mm - 1):
    fact.append((fact[i] * (i + 1)) % mod)
  invf = inved(fact[N - 1])
  for i in L:
    pad = (fact[N - 1 + i[1]] * inved(fact[i[1]]) * invf) % mod
    prod *= pad
    prod %= mod
  print(prod)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
MOD = 10**9+7
A = []
m = M
for i in range(2, int(M**0.5)+1):
    if m % i == 0:
        m //= i
        k = 1
        while m % i == 0:
            m //= i
            k += 1
        A.append(k)
        if m == 1:
            break
else:
    A.append(1)
B = [0] * max(A)
for a in A:
    B[a-1] += 1
fn_1 = 1
for i in range(1, N):
    fn_1 *= i
    fn_1 %= MOD
ans = 1
fk = fn_1
for i, b in enumerate(B, N):
    fk *= i
    fk %= MOD
    fk *= pow(max(1, i - N + 1), MOD-2, MOD)
    fk %= MOD
    ans *= pow(fk, b, MOD)
    ans %= MOD
    ans *= pow(pow(fn_1, b, MOD), MOD-2, MOD)
    ans %= MOD
print(ans)

Submission status: Wrong Answer

Solution code:

N,M=[int(x) for x in str(input()).split()]
lim=int(M**0.5)+100005

prime_sieve=[1 for i in range(lim)]


prime_sieve[0]=0
prime_sieve[1]=0

prime=[]
count=[]
check=0
for i in range(2,lim):
  if prime_sieve[i]==1:
    prime.append(i)
    count.append(0)

    for j in range(2,(lim-1)//i+1):
      prime_sieve[i*j]=0

for i in range(len(prime)):
  while M%prime[i]==0:
    check=1
    count[i]+=1
    M=M//prime[i]
  if M==1:
    break


num=10**9+7
x=1
factorial=[1]
for i in range(1,2*10**5+1):
  x=(i*x)%num
  factorial.append(x)
 
rfactorial=[]
for i in factorial:
  rfactorial.append(pow(i,num-2,num))
 

def c(n,k):
  return (((factorial[n]*rfactorial[k])%num)*rfactorial[n-k])%num


ans=1
for i in range(len(prime)):
  ans=(ans*c(N-1+count[i],count[i]))%num

if check!=0:
  print(ans)
else:
  print(N)

Submission status: Wrong Answer

Solution code:

N,M=[int(x) for x in str(input()).split()]
lim=pow(2,5)+5





num=10**9+7
x=1
factorial=[1]
for i in range(1,2*10**5+1):
  x=(i*x)%num
  factorial.append(x)
 
rfactorial=[]
for i in factorial:
  rfactorial.append(pow(i,num-2,num))
 

def c(n,k):
  return (((factorial[n]*rfactorial[k])%num)*rfactorial[n-k])%num


ans=1
for i in range(2,int(M**0.5)+1):
  count=0
  while M%i==0:
    count+=1
    M=M//i
  ans=(ans*c(N-1+count,count))%num
print(ans)

Submission status: Wrong Answer

Solution code:

N,M=[int(x) for x in str(input()).split()]
lim=int(M**0.5)+10000

prime_sieve=[1 for i in range(lim)]


prime_sieve[0]=0
prime_sieve[1]=0

prime=[]
count=[]
for i in range(2,lim):
  if prime_sieve[i]==1:
    prime.append(i)
    count.append(0)
    for j in range(2,(lim-1)//i+1):
      prime_sieve[i*j]=0

for i in range(len(prime)):
  while M%prime[i]==0:
    count[i]+=1
    M=M//prime[i]
  if M==1:
    break


num=10**9+7
x=1
factorial=[1]
for i in range(1,2*10**5+1):
  x=(i*x)%num
  factorial.append(x)
 
rfactorial=[]
for i in factorial:
  rfactorial.append(pow(i,num-2,num))
 

def c(n,k):
  return (((factorial[n]*rfactorial[k])%num)*rfactorial[n-k])%num


ans=1
for i in range(len(prime)):
  ans=(ans*c(N-1+count[i],count[i]))%num
print(ans)

Submission status: Wrong Answer

Solution code:

N,M=[int(x) for x in str(input()).split()]
lim=int(M**0.5)+2

prime_sieve=[1 for i in range(lim)]


prime_sieve[0]=0
prime_sieve[1]=0

prime=[]
count=[]
for i in range(2,lim):
  if prime_sieve[i]==1:
    prime.append(i)
    count.append(0)
    for j in range(2,(lim-1)//i+1):
      prime_sieve[i*j]=0

for i in range(len(prime)):
  while M%prime[i]==0:
    count[i]+=1
    M=M//prime[i]
  if M==1:
    break


num=10**9+7
x=1
factorial=[1]
for i in range(1,2*10**5+1):
  x=(i*x)%num
  factorial.append(x)
 
rfactorial=[]
for i in factorial:
  rfactorial.append(pow(i,num-2,num))
 

def c(n,k):
  return (((factorial[n]*rfactorial[k])%num)*rfactorial[n-k])%num
 

ans=1
for i in range(len(prime)):
  ans=(ans*c(N-1+count[i],count[i]))%num
print(ans)

Submission status: Wrong Answer

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

fct = [1]
fct2 = [m]


tmp =1
while m%2==0:
    tmp*=2
    fct.append(tmp)
    m//=2
    fct2.append(m)
m_sq = int(m**(1/2)) + 10
for i in range(3,m_sq,2):
    if m%i==0:
        fct.append(i)
        fct2.append(m//i)

fct = list(set(fct+fct2))
fct.sort()

l = len(fct)
d = {f:i for i,f in enumerate(fct)}

dp = [[0 for i in range(l)] for j in range(n)]
dp[0] = [1]*(l)

for i in range(1,n):
    for j in range(l):
        fj = fct[j]
        for k in range(j+1):
            fk = fct[k]
            if fj%fk==0:
                dp[i][j] += dp[i-1][k]
                dp[i][j] %= mod
print(dp[n-1][l-1])

Submission status: Wrong Answer

Solution code:
# ABC 110 D - Factorization
def factorization(n):
    retlist = []
    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
            retlist.append(cnt)

    if temp!=1:
        retlist.append(1)

    if retlist==[]:
        retlist.append(1)

    return retlist

def factorial_mod(n, mod):
    a = 1
    for i in range(1, n + 1):
        a *= i
        a %= mod
    return a
 
def comb_mod(n, k, mod):
    if k > n or k < 0:
        return 0
    fact_n = factorial_mod(n, mod)
    fact_k = factorial_mod(k, mod)
    fact_n_k = factorial_mod(n - k, mod)
    return (fact_n * pow(fact_k, mod - 2, mod) * pow(fact_n_k, mod - 2, mod)) % mod

n,m=map(int,input().split())
f=[]
f=factorization(m)
mod=10**9+7
ans=1
for ff in f:
    t=comb_mod(ff+n-1,ff,mod)
    ans*=t
    ans%=mod
print(ans)

Submission status: Wrong Answer

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

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())
# print(factorization(M))
a = 1
# print(factorization(M))
for fac in factorization(M):

    # print(fac[1], cmb(fac[1]+1 , N-1))
    # print(fac[1]+N-1, cmb(fac[1]+N-1 , fac[1]))

    a *= cmb(fac[1]+N-1, fac[1])
print(a % (10**9+7))

Submission status: Wrong Answer

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 not arr:
        arr.append([n, 1])

    return arr


def nCr(n,r,mod = 10**9+7):
    r = min(n-r,r)
    numer = denom = 1
    for i in range(1,r+1):
        numer = numer * (n+1-i) %mod
        denom = denom * i % mod
    return numer * pow(denom,mod-2,mod) %mod


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

ans = 1
for factor, count in factors:
    pattern = nCr(count+n-1, count)
    ans *= pattern
    ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
mod=10**9+7
def combination(n, r):
    a = 1
    b = 1
    for i in range(r):
        a *= (n - i)
        b *= (i + 1)
    return a // b
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
 
    if n > 1:
        dic[n] = 1
    return dic
d=get_prime_dic(m)
ans=1
for i,j in d.items():
    ans*=combination(n-1+j, j)%mod


print(ans)

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7
NUM_MAX = 10**5
is_prime = [True] * NUM_MAX
is_prime[0] = False
is_prime[1] = False
primes = []
for i in range(NUM_MAX):
    if is_prime[i]:
        primes.append(i)
        for j in range(2*i, NUM_MAX, i):
            is_prime[j] = False

def prime_fact(n):
    res = {}
    for p in primes:
        while n % p == 0:
            n //= p
            res[p] = res.get(p, 0) + 1
    return res

def inv_pow(a, p):
    res = 1
    while p > 0:
        if p % 2 == 1:
            res = (res * a) % MOD
        p //= 2
        a = (a * a) % MOD
    return res

def comb(n, k):
    p, q = 1, 1
    for i in range(k):
        p = p * (n - i) % MOD
        q = q * (i + 1) % MOD
    return p * inv_pow(q, MOD-2) % MOD

def solve(n, m):
    v = prime_fact(m)
    ans = 1
    for k in v.values():
        ans = ans * comb(n+k-1, k) % MOD
    return ans % MOD

assert solve(2, 6) == 4
assert solve(3, 12) == 18
assert solve(100000, 1000000000) == 957870001

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

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
def prime_factorize(x):
    a=[]
    b=[]
    while x%2==0:
        if 2 not in b:
            a.append(2)
            b.append(2)
            x/=2
        else:
            a.append(2)
            x/=2
    f=3
    while f*f<=x:
        if x%f==0:
            if f not in b:
              a.append(f)
              b.append(f)
              x/=f
            else:
              a.append(f)
              x/=f
        else:
          f+=2        
    if x!=1:
      a.append(int(x))
      b.append(int(x))
    return a,b    

def comb(n, b):
    if b > n - b:
      b = n - b
    r = 1
    for k in range(n, n-b, -1):
      r = r * k
    d = 1
    for k in range(1, b+1):
      d = d * k
    return r // d 
  
ans=1
A,B=prime_factorize(m)

for i in range(len(B)):
  c=A.count(B[i])  
  ans*=comb(c+n-1,c)
  ans%=10**9+7

print(ans)

Submission status: Wrong Answer

Solution code:
mod = 1000000007

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, y//2)**2 * x % mod

def div(a, b):
    return mul(a, pow(b, mod-2,mod))

ivl = [0]
def inverse_max(a): #下2つを使用する際の下準備

    now = 1
    for i in range(a):
        i += 1
        now *= i
        now %= mod
        ivl.append(now)

def nCr(n,r):
    return div(ivl[n] , mul(ivl[n-r] , ivl[r]))


N,M = map(int,input().split())
inverse_max(N + 40)

l = [2]
now = 3

while now ** 2 <= M:
    flag = True
    for i in l:
        if now % i == 0:
            flag = False
            break
    if flag:
        l.append(now)
    now += 2

dic = {}
for i in l:

    while M % i == 0:
        if i not in dic:
            dic[i] = 1
        else:
            dic[i] += 1

        M //= i

if M != 1:
    dic[M] = 1

ans = 1
#print (dic)

for i in dic:
    ans *= nCr(dic[i] + N - 1,dic[i])
    #print (ans)
    ans %= (10 ** 9 + 7)
print (ans % (10**9+7))

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect_left
from heapq import heappush, heappop
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()

if N == 1:
	print(1)
	sys.exit()

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

fact_max = 10**6  # 必要そうな階乗の限界を入れる
factorial = [1]
for i in range(1, fact_max):
    factorial.append(factorial[i-1] * i % mod)

def power(x, y):
    if y == 0:
        return 1
    elif y == 1:
        return x % mod
    elif y % 2 == 0:
        return power(x, int(y/2)) ** 2 % mod
    else:
        return power(x, int((y-1)/2)) ** 2 * x % mod

def C(n, r):
    return (((factorial[n] * x_inv[r]) % mod) * x_inv[n-r]) % mod

x_inv = [0] * fact_max
x_inv[-1] = power(factorial[-1], mod-2)
for i in range(fact_max-2, -1, -1):
    x_inv[i] = x_inv[i+1] * (i+1) % mod

fact = factorization(M)
ans = 1
for n, power in fact:
	ans = (ans * C(power+N-1, power))%mod

print(ans)

Submission status: Wrong Answer

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

DIV=10**9+7

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

P = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, P + 1 ):
  g1.append( ( g1[-1] * i ) % DIV )
  inverse.append( ( -inverse[DIV % i] * (DIV//i) ) % DIV )
  g2.append( (g2[-1] * inverse[-1]) % DIV )

N,M=map(int,input().split())
facs=factorization(M)
ans=1
for fac in facs:
  a,b=fac[0],fac[1]
  # 区別しないb個のモノを区別可能なN個の箱に分ける（0個の箱があってもよい）
  # (b+(N+1)) C b
  ans=((ans%DIV)*(cmb(b+(N-1),b,DIV))%DIV)%DIV

print(ans)

Submission status: Wrong Answer

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

DIV=10**9+7

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

P = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, P + 1 ):
  g1.append( ( g1[-1] * i ) % DIV )
  inverse.append( ( -inverse[DIV % i] * (DIV//i) ) % DIV )
  g2.append( (g2[-1] * inverse[-1]) % DIV )

N,M=map(int,input().split())
facs=factorization(M)
ans=1
for fac in facs:
  a,b=fac[0],fac[1]
  # 区別しないb個のモノを区別可能なN個の箱に分ける（0個の箱があってもよい）
  # (b+(N+1)) C b
  ans*=cmb(b+(N-1),b,DIV)

print(ans%DIV)

Submission status: Wrong Answer

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())
mod=10**9+7

a=factorization(m)
ans=1
for i in a:
    k=i[1]
    t=1
    for j in range(n,n+k-1+1):
        t*=j
    for j in range(1,k+1):
        t=t//j
    ans*=t
    ans%=mod
print(ans)

Submission status: Wrong Answer

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())
mod=10**9+7

a=factorization(m)
ans=1
for i in a:
    k=i[1]
    t=1
    for j in range(n+1,n+k-1+1):
        t*=j
    for j in range(1,n+1):
        t=t//j
    ans*=t
    ans%=mod
print(ans)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy,copy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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 - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def main():
    n, m = MAP()
    lis = factorization(m)
    p = 0
    for x in lis:
        p += x[1]
    #print(lis)
    #print(p)

    ans = 1
    for p, b in lis:
        ans *= cmb(b + n - 1, b)

    print(ans%mod)

if  __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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

factorial = [1]
for i in range(1, 1000000):
	factorial.append(factorial[i-1] * i % mod)
 
def power(x, y):
	if y == 0:
		return 1
	elif y == 1:
		return x % mod
	elif y % 2 == 0:
		return power(x, int(y/2)) ** 2 % mod
	else:
		return power(x, int((y-1)/2)) ** 2 * x % mod
def C(n, r):
	return (((factorial[n] * x_inv[r]) % mod) * x_inv[n-r]) % mod
 
x_inv = [0] * (1000000)
x_inv[-1] = power(factorial[-1], mod-2)
for i in range(1000000-2, -1, -1):
	x_inv[i] = x_inv[i+1] * (i+1) % mod

N, M = MAP()

fact_M = factorization(M)

ans = 1
for n in fact_M:
	ans = (ans*C(n[1]+N-1, n[1]))%mod
print(ans)

Submission status: Wrong Answer

Solution code:
# D - Factorization
# Mの素因数の順列(重複考慮)パターンに、数列のうちそれらが入る場所のパターンをかける(素因数以外の場所は1で埋める)

import math, collections, itertools

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

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

# n以下の全ての素数のセットを返す関数
def prime_set(n):
    primes = set(range(2, n+1))
    for i in range(2, int(n**0.5) + 1):
        primes.difference_update(range(i*2, n+1, i))
    return primes

# nを素因数分解して素因数の全リストを返す関数
def prime_factors_duplicating_list(n):
    f = []
    for i in prime_set(int(n**0.5) + 1):
        while n % i == 0:
            f.append(i)
            n //= i
    if n > 1:
        f.append(n)
    return f

# 数列に組み込む因数のリストを与えると、その因数を含み条件を満たす数列の個数を返す関数
def cal_pattern(M_div):
    M_div_dict = collections.Counter(M_div)
    dup = 1
    for key in M_div_dict:
        dup *= math.factorial(M_div_dict[key])
            
    perm_M_div = math.factorial(len(M_div)) // dup
    
    tmp, tmp2 = 1, N
    for _ in range(len(M_div)):
        tmp *= tmp2
        tmp2 -= 1
    comb_M_div_in_seq = tmp // math.factorial(len(M_div)) # 毎回N!を計算しないように注意。N >> len(M_div)
    
    return (perm_M_div * comb_M_div_in_seq) % MOD


M_pf = prime_factors_duplicating_list(M)

ans = 0
memo = set()

# Mの素因数リスト(あまり長くならない)から2つ選んで乗算して合成し、新しいMの因数リストを作る。これを繰り返す
# 検討済みの因数リストだった場合はpass
for n_compose in range(1, len(M_pf)+1):
    for compose_indices in itertools.combinations(range(len(M_pf)), n_compose):
        tmp = 1
        for idx in compose_indices:
            tmp *= M_pf[idx]
        M_div = [tmp]
        for idx in range(len(M_pf)):
            if idx not in compose_indices:
                M_div.append(M_pf[idx])
        M_div.sort()
        if tuple(M_div) not in memo and len(M_div) <= N:
            memo.add(tuple(M_div))
            ans += cal_pattern(M_div)
            ans %= MOD
           # print(M_div, cal_pattern(M_div))

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N, M = map(int, input().split())

mod = 10 ** 9 + 7

fac = [1]
inv = [1]
for i in range(1, N + 1) :
    fac.append(fac[-1] * i % mod)
    inv.append(pow(fac[-1], mod - 2, mod))

def rec(m, pre_divisor, divisors, lev) :
    ret = 0
    if lev == N :
        comb = fac[N]
        for c in Counter(divisors + [m]).values() :
            comb *= inv[c]
            comb %= mod
        ret += comb
        ret %= comb
        return ret
    
    i = pre_divisor
    while i * i <= m :
        if m % i == 0 :
            ret += rec(m // i, i, divisors + [i], lev + 1)
        i += 1
    
    comb = fac[N]
    for c in Counter(divisors + [m]).values() :
        comb *= inv[c]
        comb %= mod
    comb *= inv[N-lev-1]
    comb %= mod
    ret += comb
    ret %= mod
    return ret
    
print(rec(M, 2, [], 0))

Submission status: Wrong Answer

Solution code:
mod=10**9+7
def prime_factor(n):
  ass=[]
  for i in range(2,int(n**0.5)+1):
    while n%i==0:ass.append(i);n//=i
  if n!=1:ass.append(n)
  return ass
f=[1]
for i in range(1,200000):f.append(f[-1]*i%mod)
def comb(a,b,m):return f[a]*pow(f[b],m-2,m)*pow(f[a-b],m-2,m)%m

n,m=map(int,input().split())
d=prime_factor(m)
b=[1]
for i in range(1,len(d)):
  if d[i-1]==d[i]:b[-1]+=1
  else:b.append(1)
ans=1
for i in b:ans*=comb(i+n-1,i,mod);ans%=mod
print(ans)

Submission status: Wrong Answer

Solution code:
def shave(m):
    m_root = int(m**0.5)
    candidate = [i for i in range(3,m+1,2)]
    for i in range(3,m_root+2,2):
        candidate = [ j for j in candidate if j == i or j % i != 0]   
    candidate = [2] + candidate
    return candidate

def comb(a,b,m):
	if b == 0 or b == a:
		ret = 1
	else:
		ret = 1
		for i in range(a-b+1,a+1):
			ret = (ret * i) % m
		for i in range(1,b+1):
			ret = (ret * pow(i,m-2,m) ) % m
	return ret

mod = 10**9+7
prime_list = shave(int(33333))

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

p_list = []

for i in prime_list:
    if m == 1:
        break
    elif m % i == 0:
        q = 0
        while m % i == 0:
            m //= i
            q += 1
        p_list.append(q)

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

Submission status: Wrong Answer

Solution code:
def fact(n):
    global mod
    if n==0:
        return 1
    else:
        res=1
        for i in range(1,n+1):
            res=(res*i)%mod
        return res

def inv(n):
    global mod
    res=1
    prod=n%mod
    a=mod-2
    while a>0:
        if a%2==1:
            res=(res*prod)%mod
        a//=2
        prod=(prod**2)%mod
    return res

def combi(n,r):
    return (fact(n)*inv(fact(r))*inv(fact(n-r)))%mod

def ord(n,p):
    res=0
    while n%p==0:
        res+=1
        n//=p
    return res

mod=10**9+7
N,M=map(int,input().split())
l=[]

if ord(M,2)>0:
    l.append(ord(M,2))
    M//=2**ord(M,2)

p=3
while M>1 and p<=int(10**4.5):
    if ord(M,p)>0:
        l.append(ord(M,p))
        M//=p**ord(M,p)
    p+=2
if M>1:
    l.append(1)
    M=1

print(l)

ans=1
for e in l:
    ans=(ans*combi(e+N-1,N-1))%mod

print(ans)

Submission status: Wrong Answer

Solution code:
def resolve():
    N,M = map(int,input().split())
    import sys
    def primes(m):
        temp = m
        a = []
        if temp % 2 == 0:
            a.append(1)
            temp //= 2
            while(temp % 2 == 0):
                a[0] += 1
                temp //= 2
        p = 3
        while(p*p < m):
            if temp % p == 0:
                a.append(1)
                temp //= p
                while(temp % p == 0):
                    a[-1] += 1
                    temp //= p
            p += 2
        if temp != 1:
            a.append(1)
        return a
    prime_list = primes(M)
    if prime_list == []:
        print(1)
        sys.exit()
    H = [0 for _ in range(max(prime_list)+1)]
    H[0] = 1
    for k in range(max(prime_list)):
        H[k+1] = (N+k) * H[k] // (k+1) % int(1e9+7)
    ans = 1
    for pr in prime_list: 
        ans *= H[pr]
        ans %= int(1e9+7)
    print(ans)
resolve()

Submission status: Wrong Answer

Solution code:
N, M = list(map(int, input().split(' ')))
MOD = int(1e9 + 7)
seeds = []
p = 2
while p*p > M:
  while M % p == 0:
    seeds.append(p)
    M = M // p
  p += 1
if M > 1:
  seeds.append(M)
 
def comb(n, k):
  ans = 1
  for i in range(1, k + 1):
    ans = (ans * (n + 1 - i) // i)
  return ans
 
ans = 1
hogehoge = set(seeds)
for i in hogehoge:
  a_ct = seeds.count(i)
  ans = (ans * comb(a_ct + N-1, min(a_ct, N-1))) % MOD
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = list(map(int, input().split(' ')))
MOD = int(1e9 + 7)
primes = []
if M % 2 == 0:
  primes.append(2)

seeds = []
p = 2
while M:
  while M % p == 0:
    seeds.append(p)
    M = M // p
  if p*p > M:
    seeds.append(M)
    M = 0
  p += 1

def comb(n, k):
  ans = 1
  for i in range(1, k + 1):
    ans = (ans * (n + 1 - i) // i)
  return ans

ans = 1
hogehoge = set(seeds)
for i in hogehoge:
  a_ct = seeds.count(i)
  ans = (ans * comb(a_ct + N-1, min(a_ct, N-1))) % MOD
print(ans)

Submission status: Wrong Answer

Solution code:
import math
N, M = list(map(int, input().split(' ')))
MOD = int(1e9 + 7)
primes = []
if M % 2 == 0:
  primes.append(2)
def is_prime(n):
  for i in range(len(primes)):
    if n % primes[i] == 0:
      return False
  return True
sq1e9 = int((1e9) ** 0.5) + 1
for i in range(3, sq1e9):
  if is_prime(i):
    primes.append(i)

seeds = []
for p in primes:
  while M % p == 0:
    seeds.append(p)
    M = M // p

def comb(n, k):
  ans = 1
  for i in range(1, k + 1):
    ans = (ans * (n + 1 - i) // i)
  return ans

ans = comb(len(seeds)-1, N-1)
# !!! 24=(2^a1 * 3^b1) * (2^a2 * 3^b2) * ... | sum(a) = 3, sub(b) = 1, len(a) = 4
# aのパターン数は 3,0,0,0 = ooo|||, 2,1,0,0 = oo|o|| なので並び替えのパターン数で
# (sum(a) + 分ける数)! / (sum(a)! * 分ける数!) = (6!/(3!3!)) = 20
# b にも同じことをして 1,0,0,0 = o||| = (1+3)!/(1!*3!) = 4
# 24を4つに分けるパターンは 20 * 4 = 80?

# (a+b)!/(a!b!) = (a+b)Ca = (a+b)Cb

ans = 1
hogehoge = set(seeds)
for i in hogehoge:
  a_ct = seeds.count(i)
  ans = (ans * comb(a_ct + N-1, min(a_ct, N-1))) % MOD
print(ans)

Submission status: Wrong Answer

Solution code:
import math
N, M = list(map(int, input().split(' ')))
MOD = int(1e9 + 7)
primes = []
if M % 2 == 0:
  primes.append(2)
def is_prime(n):
  for i in range(len(primes)):
    if n % primes[i] == 0:
      return False
  return True
for i in range(3, int(1e5)):
  if is_prime(i):
    primes.append(i)
  if i*i > N:
    break

seeds = []
for p in primes:
  while M % p == 0:
    seeds.append(p)
    M = M // p

def comb(n, k):
  ans = 1
  for i in range(1, k + 1):
    ans = (ans * (n + 1 - i) // i)
  return ans

ans = comb(len(seeds)-1, N-1)
# !!! 24=(2^a1 * 3^b1) * (2^a2 * 3^b2) * ... | sum(a) = 3, sub(b) = 1, len(a) = 4
# aのパターン数は 3,0,0,0 = ooo|||, 2,1,0,0 = oo|o|| なので並び替えのパターン数で
# (sum(a) + 分ける数)! / (sum(a)! * 分ける数!) = (6!/(3!3!)) = 20
# b にも同じことをして 1,0,0,0 = o||| = (1+3)!/(1!*3!) = 4
# 24を4つに分けるパターンは 20 * 4 = 80?

# (a+b)!/(a!b!) = (a+b)Ca = (a+b)Cb

ans = 1
hogehoge = set(seeds)
for i in hogehoge:
  a_ct = seeds.count(i)
  ans = (ans * comb(a_ct + N-1, min(a_ct, N-1))) % MOD
print(ans)