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: Runtime Error

Solution code:
from collections import defaultdict


def eratosthenes_generator():
    yield 2
    n = 3
    h = {}
    while True:
        m = n
        if n in h:
            b = h[n]
            m += 2 * b
            while m in h:
                m += 2 * b
            h[m] = b
            del h[n]
        else:
            m += 2 * n
            while m in h:
                m += 2 * n
            h[m] = n
            yield n
        n += 2


def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(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)
    k = n
    for p in eratosthenes_generator():
        while True:
            d, m = divmod(k, p)
            if m == 0:
                f[p] += 1
                k = d
            else:
                break
        if k == 1:
            break
    return f


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

Submission status: Runtime Error

Solution code:
n,m=map(int,raw_input().split())
u = set()
for k in range(1,m+1):
  if k*k>m:break
  if m%k==0:
    u.add(k); u.add(m/k)
u = list(u)
ret = [0 for _ in u]
ret[-1]=1
for _ in range(n):
  nret = [0 for _ u]
  for i,a in enumerate(u):
    for j,b in enumerate(v):
      if b%a==0:nret[i] += ret[j]
  ret = nret
print ret[0]%(10**9+7)

Submission status: Runtime Error

Solution code:
import math
N,M=map(int,input().split())
def primecheck(K):
    A=int(math.sqrt(K))+1
    for i in range(2,A+1):
        if K%i==0:
            return i
    return 1
D=dict()
while(True):
    X=int(math.sqrt(M))+1
    for i in range(2,X+1):
        if M%i==0:
            while(True):
                if i in D:
                    D[i]+=1
                else:
                    D[i]=1
                M=M//i
                if M%i!=0:
                    break
    j=primecheck(M)
    if j==1:
        if M==1:
            break
        D[M]=1
        break
    else:
        if j in D:
            D[j]=1
        else:
            D[j]+=1
P=10**9+7
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
def inv(x):
    return egcd(x,P)[0]
Y=2*N
Fact=[0 for i in range(Y+1)]
Finv=[0 for i in range(Y+1)]
Fact[0]=1
Finv[0]=1
for i in range(Y):
    Fact[i+1]=(Fact[i]*(i+1))%P
    Finv[i+1]=inv(Fact[i+1])%P
def C(n,k):
    return (Fact[n]*(Finv[k]*Finv[n-k])%P)%P
ans=1
for p in D:
    e=D[p]
    ans=ans*C(e+N-1,N-1)
    ans=ans%P
print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,raw_input().split())
u = set()
for k in range(m):
  if k*k>n:break
  if m%k==0:
    u.add(k); u.add(m/k)
u = list(u)
ret = [0 for _ u]
ret[-1]=1
for _ in range(n):
  nret = [0 for _ u]
  for i,a in enumerate(u):
    for j,b in enumerate(v):
      if b%a==0:nret[i] += ret[j]
  ret = nret
print ret[0]%(10**9+7)