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: Accepted

Solution code:
import sys
from collections import deque
import copy

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 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 get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline


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]), int(input_raw[1])]

    prime_table = prime_decomposition(M)
    primes = {}
    for p in prime_table:
        if p in primes:
            primes[p] += 1
        else:
            primes[p] = 1

    cmb = comb_calclator(10 * N, int(1e+9) + 7)
    count = 1
    for p in primes:
        b = primes[p]
        count = (count * cmb.comb(b + N - 1, b))%(int(1e+9) + 7)


    print count



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import sqrt
from collections import defaultdict

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

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

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

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

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

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

i = 2

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

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

n -= 1
ans = 1

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

print(ans)

Submission status: Accepted

Solution code:
import math

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

s=0

for i in range(2, m+2):
#     print(i)
    cnt = 0
    while m%i==0:
        m=m//i
        cnt += 1

    if cnt>0:
        t[i]=cnt

    if m==1:
        break

# if m!=1:
#     t[m]=1

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

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

Submission status: Accepted

Solution code:
import math

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

s=0

# line = [2, 3] + [i%2*2 + i//2 * 6 + 5 for i in range(a)]
# line = [2] + list(range(3, m+2, 2))

# for i in line:
for i in range(2, a+2):
#     print(i)
    cnt = 0
    while m%i==0:
        m=m//i
        cnt += 1

    if cnt>0:
        t[i]=cnt

    if m==1:
        break

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

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

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

Submission status: Accepted

Solution code:
import math

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

s=0

line = [2, 3] + [i%2*2 + i//2 * 6 + 5 for i in range(a)]
# line = [2] + list(range(3, m+2, 2))

for i in line:
# for i in range(2, m+2, 2):
#     print(i)
    cnt = 0
    while m%i==0:
        m=m//i
        cnt += 1

    if cnt>0:
        t[i]=cnt

    if m==1:
        break

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

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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Combination:
    def __init__(self, n, mod):

        g1 = [1, 1]
        g2 = [1, 1]
        inverse = [0, 1]
        for i in range(2, n + 1):
            g1.append((g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod//i)) % mod)
            g2.append((g2[-1] * inverse[-1]) % mod)
        self.MOD = mod
        self.N = n
        self.g1 = g1
        self.g2 = g2
        self.inverse = inverse

    def __call__(self, n, r):
        if (r < 0 or r > n):
            return 0
        r = min(r, n-r)
        return self.g1[n] * self.g2[r] * self.g2[n-r] % self.MOD


def fs(n):
    f = Counter()
    for i in range(2, math.ceil(math.sqrt(n)) + 1):
        error_print(i)
        if i > n:
            break
        while n % i == 0:
            f[i] += 1
            n /= i
    if n != 1:
        f[n] = 1
    return f


mod = 10**9 + 7


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


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


def mod_div(a, b):
    return mod_mul(a, mod_power(b, mod-2))


def P(n):
    ans = 1
    for i in range(2, n+1):
        ans = mod_mul(ans, i)

    return ans


@mt
def slv(N, M):
    f = fs(M)
    ans = 1
    error_print(f)
    C = Combination(10**6, mod)

    for k in f:
        ans = mod_mul(ans, C(N+f[k]-1, f[k]) % mod)
    return ans


def main():
    N, M = read_int_n()
    print(slv(N, M))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter

def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

def nCr(n, r):
    # 10C7 = 10C3
    r = min(r, n-r)

    # Calculate the numerator.
    numerator = 1
    for i in range(n, n-r, -1):
        numerator *= i

    # Calculate the denominator. Should use math.factorial?
    denominator = 1
    for i in range(r, 1, -1):
        denominator *= i

    return numerator // denominator

if __name__ == '__main__':
    n, m = map(int, input().split())
    ans = 1
    cnt = Counter(prime_factors(m))
    for i in cnt.values():
        ans *= nCr(i+n-1, i)
        ans %= 10**9+7
    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict


def prepare(n, MOD):
    f = 1
    factorials = [1] * (n + 1)
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials[m] = f
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return factorials, invs


def prime_factorize(n):
    f = defaultdict(lambda: 0)
    f[2] = len(bin(n & -n)) - 3
    i = 3
    k = n >> f[2]
    limit = k ** 0.5
    while 1 < k and i <= limit:
        while True:
            d, m = divmod(k, i)
            if m == 0:
                f[i] += 1
                k = d
                limit = k ** 0.5
            else:
                break
        i += 2
    if k > 1:
        f[k] = 1
    return f


MOD = 1000000007
n, m = map(int, input().split())
pf = prime_factorize(m)
mx = max(pf.values())
f, r = prepare(n + mx - 1, MOD)
ans = 1
for p, e in pf.items():
    ans *= f[n + e - 1]
    ans %= MOD
    ans *= r[n - 1]
    ans %= MOD
    ans *= r[e]
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict


def prepare(n, MOD):
    f = 1
    factorials = [1] * (n + 1)
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials[m] = f
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return factorials, invs


def prime_factorize(n):
    f = defaultdict(lambda: 0)
    f[2] = len(bin(n & -n)) - 3
    i = 3
    k = n >> f[2]
    limit = k ** 0.5
    while 1 < k and i <= limit:
        while True:
            d, m = divmod(k, i)
            if m == 0:
                f[i] += 1
                k = d
            else:
                break
        i += 2
    if k > 1:
        f[k] = 1
    return f


MOD = 1000000007
n, m = map(int, input().split())
pf = prime_factorize(m)
mx = max(pf.values())
f, r = prepare(n + mx - 1, MOD)
ans = 1
for p, e in pf.items():
    ans *= f[n + e - 1]
    ans %= MOD
    ans *= r[n - 1]
    ans %= MOD
    ans *= r[e]
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
from math import factorial
Q = 10**9+7
def primes(n):
    primfac = [0]
    d = 2
    while d*d <= n:
        while n%d == 0:
            primfac[-1] += 1
            n //= d
        d += 1
        if primfac[-1] != 0:
            primfac.append(0)
    if n > 1:
        if primfac[-1] == 0:
            primfac[-1] += 1
        else:
            primfac.append(1)
    return primfac
N, M = map( int, input().split())
C = primes(M)
ans = 1
if N == 1:
    print(1)
else:
    for x in C:
        for i in range(x):
            ans *= N+i
        ans //= factorial(x)
        ans = ans%Q
    print(ans)

Submission status: Accepted

Solution code:
import math
from collections import defaultdict

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

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

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

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

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

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

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

i = 2

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

if not A:
    print(n)
    exit()

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

n -= 1
ans = 1

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

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from math import sqrt
n,m = (int(i) for i in input().split())
if m==1: ans = 1
else:
	m2,k,x,mod,ans = m,2,[],10**9+7,1
	while k**2<=m2:
		for i in range(k,int(sqrt(m2))+1):
			if m2%i==0:
				x.append(i)
				k,m2 = i,m2//i
				break
			elif i==int(sqrt(m2)): k = i+1
	x.append(m2)
	c,d = Counter(x).most_common(),[]
	for i,j in c: d.append(j)
	n2 = max(d)+n
	fn,fk = [1]*(n2),[1]*(n2)
	for i in range(n2-1): fn[i+1] = (fn[i]*(i+2))%mod
	def power(n,k):
		if k==1: return n
		elif k%2==0: return power((n**2)%mod,k//2)
		else: return (n*power(n,k-1))%mod
	def comb(n,k):
		if n==0 or k==0 or n==k: return 1
		else: return (((fn[n-1]*fk[n-k-1])%mod)*fk[k-1])%mod
	fk[-1] = power(fn[-1],mod-2)
	for i in range(2,n2+1): fk[-i] = (fk[-i+1]*(n2+2-i))%mod
	for i in d: ans = (ans*comb(i+n-1,i))%mod
print(ans)