Problem p03253 (python)

Fixed submission:
# encoding: utf-8
import math
N, M = map(int, input().split())

ips = []
M_tmp = M
for p in range(2, int(math.sqrt(M)) + 1):
    if M_tmp % p > 0: continue
    for i_p in range(1, 33):
        if M_tmp % (p ** (i_p + 1)) > 0: break
    ips.append(i_p)
    M_tmp = M_tmp // (p ** i_p)
    if M_tmp == 1: break
else:
    ips.append(1)

#### O(NlogM) below ?
# create memo
## init
if len(ips) > 0: ip_max = max(ips)
else: ip_max = 0
memo = [[None] * N for i in range(ip_max + 1)] # max ip
for j in range(N): memo[0][j] = 1
for i in range(1, ip_max + 1): memo[i][N - 1] = 1
## fill
for i in range(1, ip_max + 1):
    sum_tmp = 0
    vals = list(memo[i - 1])[::-1]
    ptr_memo = memo[i]
    for j, val in enumerate(vals):
        sum_tmp += val
        ptr_memo[N - 1 - j] = sum_tmp
#### O(NlogM) above ?
        
# calculate ans
ans = 1
for i_p in ips:
    ans = (ans * memo[i_p][0]) % (10 ** 9 + 7)

if M == 1: print(1)
elif ip_max < 1: print(N)
else: print(ans)

Buggy submission (verdict: Runtime Error):
# encoding: utf-8
import math, random
N, M = map(int, input().split())

def distribute(pos, full, tmp):
    return memo[tmp][pos]

def f1(x, c, n):
    return (x ** 2 + c) % n

def gcd(a, b):
    if b < 1: return a
    else: return gcd(b, a % b)

def pra(n, c):
    # print("######", n, c)
    if n % 2 == 0: return 2
    elif prime(n) == True: return n
    x = y = 2
    d = 1
    while d == 1:
        x = f1(x, c, n)
        y = f1(f1(y, c, n), c, n)
        d = gcd(n, int(math.fabs(x - y)))
    return pra(d, c + 1)
    
def jaeschke(n):
    d2s = n - 1
    for s in range(1, 32):
        if d2s % (2 ** (s + 1)) > 0: break
    d = d2s // (2 ** s)
    # print("###", n, d, s)
    for a in (2, 7, 61): 
        if (a ** d) % n == 1: continue
        for r in range(s):
            if (a ** (d * (2 ** r))) % n == n - 1: break
        else:
            return False
    else:
        return True

def prime(n):
    # print("####", n)
    if n == 2: return True
    elif n % 2 == 0: return False
    else: return jaeschke(n)

def pf(X):
    X_tmp = X
    ips = []
    c = 1
    for i in range(32):
        for c in range(1, 2):
            d = pra(X_tmp, c)
            if d > -1: break
        # print("##", X_tmp, d, c)
        for i_p in range(1, 32):
            if X_tmp % (d ** (i_p + 1)) > 0: break
        # print("#", X_tmp, d, i_p)
        X_tmp = X_tmp // (d ** i_p)
        ips.append(i_p)
        if X_tmp == 1: break
    else:
        # print("#", X_tmp, X_tmp, 1)
        ips.append(1)
    return ips

ips = pf(M)
    
#### O(NlogM) below ?
# create memo
## init
if len(ips) > 0: ip_max = max(ips)
else: ip_max = 0
memo = [[None] * N for i in range(ip_max + 1)] # max ip
for j in range(N): memo[0][j] = 1
for i in range(1, ip_max + 1): memo[i][N - 1] = 1
## fill
for i in range(1, ip_max + 1):
    sum_tmp = 0
    vals = list(memo[i - 1])[::-1]
    p_memo = memo[i]
    for j, val in enumerate(vals):
        sum_tmp += val
        p_memo[N - 1 - j] = sum_tmp
#### O(NlogM) above ?
        
# calculate ans
ans = 1
for i_p in ips: ans = (ans * distribute(0, i_p, i_p)) % (10 ** 9 + 7)

if M == 1: print(1)
elif ip_max < 1: print(N)
else: print(ans)

Buggy submission (verdict: Runtime Error):
# encoding: utf-8
import math, random
N, M = map(int, input().split())

def distribute(pos, full, tmp):
    return memo[tmp][pos]

# # define search range
# p_max = M // 2 # M is prime if M has a factor p (> p_max)
# ip_up = max((1, int(math.log2(M)))) # MDE
#
# #### O(MlogM) below (if M has a very large prime factor)
# M_tmp = M
# ips = []
# for p in range(2, p_max + 1):
#     if M_tmp % p > 0: continue
#     # how many times M_tmp can be divided
#     p_tmp = p
#     for i_p in range(ip_up + 1):
#         if M_tmp % p_tmp > 0: break
#         p_tmp = p_tmp * p
#     # calculate later
#     ips.append(i_p)
#     # next
#     M_tmp = M_tmp // (p_tmp // p)
#     if M_tmp == 1: break
# #### O(Mlog M) above

def lcg(x, c, n):
    return (x ** 2 + c) % n

def gcd(a, b):
    if b < 1: return a
    else: return gcd(b, a % b)

def pra(n, c):
    # print("######", n, c)
    x = y = 2
    d = 1
    while d == 1:
        x = lcg(x, c, n)
        y = lcg(lcg(y, c, n), c, n)
        d = gcd(n, int(math.fabs(x - y)))
        # print("#####", x, y, d)
    if prime(d) == True: return d
    elif d % 2 == 0: return 2 # prime factor 2 cannot be found ?
    elif d == n: return pra(n, c + 1)
    else: return pra(d, 1)
    
def jaeschke(n):
    d2s = n - 1
    for s in range(1, 32):
        if d2s % (2 ** (s + 1)) > 0: break
    d = d2s // (2 ** s)
    # print("###", n, d, s)
    for a in (2, 7, 61): 
        if (a ** d) % n == 1: continue
        for r in range(s):
            if (a ** (d * (2 ** r))) % n == n - 1: break
        else:
            return False
    else:
        return True

def prime(n):
    # print("####", n)
    if n == 2: return True
    elif n % 2 == 0: return False
    else: return jaeschke(n)

def pf(X):
    X_tmp = X
    ips = []
    c = 1
    for i in range(32):
        d = pra(X_tmp, c)
        # print("##", X_tmp, d, c)
        for i_p in range(1, 32):
            if X_tmp % (d ** (i_p + 1)) > 0: break
        # print("#", X_tmp, d, i_p)
        X_tmp = X_tmp // (d ** i_p)
        ips.append(i_p)
        if X_tmp == 1: break
    else:
        # print("#", X_tmp, X_tmp, 1)
        ips.append(1)
    return ips

ips = pf(M)
    
#### O(NlogM) below ?
# create memo
## init
if len(ips) > 0: ip_max = max(ips)
else: ip_max = 0
memo = [[None] * N for i in range(ip_max + 1)] # max ip
for j in range(N): memo[0][j] = 1
for i in range(1, ip_max + 1): memo[i][N - 1] = 1
## fill
for i in range(1, ip_max + 1):
    sum_tmp = 0
    vals = list(memo[i - 1])[::-1]
    p_memo = memo[i]
    for j, val in enumerate(vals):
        sum_tmp += val
        p_memo[N - 1 - j] = sum_tmp
#### O(NlogM) above ?
        
# calculate ans
ans = 1
for i_p in ips: ans = (ans * distribute(0, i_p, i_p)) % (10 ** 9 + 7)

if M == 1: print(1)
elif ip_max < 1: print(N)
else: print(ans)

Buggy submission (verdict: Runtime Error):
# encoding: utf-8
import math
N, M = map(int, input().split())

def distribute(pos, full, tmp):
    return memo[tmp][pos]

# define search range
p_max = int(M / 2) # M is prime if M has a factor p (> p_max)
ip_up = int(math.log2(p_max))

#### O(MlogM) below (if M has a very large prime factor)
M_tmp = M
ips = []
for p in range(2, p_max + 1):
    if M_tmp % p > 0: continue
    # how many times M_tmp can be divided
    p_tmp = p
    for i_p in range(ip_up + 1):
        if M_tmp % p_tmp > 0: break
        p_tmp = p_tmp * p
    # calculate later
    ips.append(i_p)
    # next
    M_tmp = M_tmp // (p_tmp // p)
    if M_tmp == 1: break
#### O(Mlog M) above

#### O(N) below
# create memo
## init
if len(ips) > 0: ip_max = max(ips)
else: ip_max = 0
memo = [[None] * N for i in range(ip_max + 1)] # max ip
for j in range(N): memo[0][j] = 1
for i in range(1, ip_max + 1): memo[i][N - 1] = 1
## fill
for i in range(1, ip_max + 1):
    sum_tmp = 0
    vals = list(memo[i - 1])[::-1]
    p_memo = memo[i]
    for j, val in enumerate(vals):
        sum_tmp += val
        p_memo[N - 1 - j] = sum_tmp
#### O(N) above
        
# calculate ans
ans = 1
for i_p in ips: ans = (ans * distribute(0, i_p, i_p)) % (10 ** 9 + 7)

if ip_max == 0: print(N)
else: print(ans)

Buggy submission (verdict: Runtime Error):
# encoding: utf-8
import math
N, M = map(int, input().split())

def distribute(pos, full, tmp):
    return memo[tmp][pos]

# define search range
p_max = int(M / 2) # M is prime if M has a factor p (> p_max)
ip_up = int(math.log2(p_max))

#### O(MlogM) below (if M has a very large prime factor)
M_tmp = M
ips = []
for p in range(2, p_max + 1):
    if M_tmp % p > 0: continue
    # how many times M_tmp can be divided
    p_tmp = p
    for i_p in range(ip_up + 1):
        if M_tmp % p_tmp > 0: break
        p_tmp = p_tmp * p
    # calculate later
    ips.append(i_p)
    # next
    M_tmp = M_tmp // (p_tmp // p)
    if M_tmp == 1: break
#### O(Mlog M) above

#### O(N) below
# create memo
## init
if len(ips) > 0: ip_max = max(ips)
else: ip_max = 0
memo = [[None] * N for i in range(ip_max + 1)] # max ip
for j in range(N): memo[0][j] = 1
for i in range(1, ip_max + 1): memo[i][N - 1] = 1
## fill
for i in range(1, ip_max + 1):
    sum_tmp = 0
    vals = list(memo[i - 1])[::-1]
    p_memo = memo[i]
    for j, val in enumerate(vals):
        sum_tmp += val
        p_memo[N - 1 - j] = sum_tmp
#### O(N) above
        
# calculate ans
ans = 1
for i_p in ips: ans = (ans * distribute(0, i_p, i_p)) % (10 ** 9 + 7)

if ip_max = 0: print(N)
else: print(ans)

Buggy submission (verdict: Runtime Error):
# encoding: utf-8
import math
N, M = map(int, input().split())

def distribute(pos, full, tmp):
    return memo[tmp][pos]

# define search range
p_max = int(M / 2) # M is prime if M has a factor p (> p_max)
ip_up = int(math.log2(p_max))

#### O(MlogM) below (if M has a very large prime factor)
M_tmp = M
ips = []
for p in range(2, p_max + 1):
    if M_tmp % p > 0: continue
    # how many times M_tmp can be divided
    p_tmp = p
    for i_p in range(ip_up + 1):
        if M_tmp % p_tmp > 0: break
        p_tmp = p_tmp * p
    # calculate later
    ips.append(i_p)
    # next
    M_tmp = M_tmp // (p_tmp // p)
    if M_tmp == 1: break
#### O(Mlog M) above

#### O(N) below
# create memo
## init
if len(ips) > 0: ip_max = max(ips)
else: ip_max = 0
memo = [[None] * N for i in range(ip_max + 1)] # max ip
for j in range(N): memo[0][j] = 1
for i in range(1, ip_max + 1): memo[i][N - 1] = 1
## fill
for i in range(1, ip_max + 1):
    sum_tmp = 0
    vals = list(memo[i - 1])[::-1]
    p_memo = memo[i]
    for j, val in enumerate(vals):
        sum_tmp += val
        p_memo[N - 1 - j] = sum_tmp
#### O(N) above
        
# calculate ans
ans = 1
for i_p in ips: ans = (ans * distribute(0, i_p, i_p)) % (10 ** 9 + 7)
    
print(ans)

Buggy submission (verdict: Runtime Error):
# encoding: utf-8
import math
N, M = map(int, input().split())

def distribute(pos, full, tmp):
    return memo[tmp][pos]

# define search range
p_max = int(M / 2) # M is prime if M has a factor p (> p_max)
ip_up = int(math.log2(p_max))

#### O(MlogM) below (if M has a very large prime factor)
M_tmp = M
ips = []
for p in filter(lambda x: M % x == 0, range(2, p_max + 1)):
    # how many times M_tmp can be divided
    p_tmp = p
    for i_p in range(ip_up + 1):
        if M_tmp % p_tmp > 0: break
        p_tmp = p_tmp * p
    # escape if M_tmp cannot be divided
    if i_p < 1: continue
    # calculate later
    ips.append(i_p)
    # next
    M_tmp = M_tmp // (p_tmp // p)
    if M_tmp == 1: break
#### O(Mlog M) above

#### O(N) below
# create memo
## init
if len(ips) > 0: ip_max = max(ips)
else: ip_max = 0
memo = [[None] * N for i in range(ip_max + 1)] # max ip
for j in range(N): memo[0][j] = 1
for i in range(1, ip_max + 1): memo[i][N - 1] = 1
## fill
for i in range(1, ip_max + 1):
    sum_tmp = 0
    vals = list(memo[i - 1])[::-1]
    p_memo = memo[i]
    for j, val in enumerate(vals):
        sum_tmp += val
        p_memo[N - 1 - j] = sum_tmp
#### O(N) above
        
# calculate ans
ans = 1
for i_p in ips: ans = (ans * distribute(0, i_p, i_p)) % (10 ** 9 + 7)
    
print(ans)

Buggy submission (verdict: Runtime Error):
# encoding: utf-8
import math
N, M = map(int, input().split())

def distribute(pos, full, tmp):
    return memo[tmp][pos]

# define search range
p_max = int(M / 2) # M is prime if M has a factor p (> p_max)
ip_up = int(math.log2(p_max))

#### O(MlogM) below (if M has a very large prime factor)
M_tmp = M
ips = []
psuedo_primes = [max((2, 2 * i + 1)) for i in range(p_max // 2)]
for p in psuedo_primes:
    # how many times M_tmp can be divided
    p_tmp = p
    for i_p in range(ip_up + 1):
        if M_tmp % p_tmp > 0: break
        p_tmp = p_tmp * p
    # escape if M_tmp cannot be divided
    if i_p < 1: continue
    # calculate later
    ips.append(i_p)
    # next
    M_tmp = M_tmp // (p_tmp // p)
    if M_tmp == 1: break
#### O(Mlog M) above

#### O(N) below
# create memo
## init
if len(ips) > 0: ip_max = max(ips)
else: ip_max = 0
memo = [[None] * N for i in range(ip_max + 1)] # max ip
for j in range(N): memo[0][j] = 1
for i in range(1, ip_max + 1): memo[i][N - 1] = 1
## fill
for i in range(1, ip_max + 1):
    sum_tmp = 0
    vals = list(memo[i - 1])[::-1]
    p_memo = memo[i]
    for j, val in enumerate(vals):
        sum_tmp += val
        p_memo[N - 1 - j] = sum_tmp
#### O(N) above
        
# calculate ans
ans = 1
for i_p in ips: ans = (ans * distribute(0, i_p, i_p)) % (10 ** 9 + 7) # oh...
    
print(ans)

Buggy submission (verdict: Runtime Error):
# encoding: utf-8
import math
N, M = map(int, input().split())

def distribute(pos, full, tmp):
    return memo[tmp][pos]

# define search range
p_max = int(M / 2) # M is prime if M has a factor p (> p_max)
ip_max = int(math.log2(M))

M_tmp = M
ips = []
for p in range(2, p_max + 1):
    # how many times M_tmp can be divided
    p_tmp = p
    for i_p in range(ip_max + 1):
        if M_tmp % p_tmp > 0: break
        p_tmp = p_tmp * p
    # escape if M_tmp cannot be divided
    if i_p < 1: continue
    # calculate later
    ips.append(i_p)
    # next
    M_tmp = M_tmp // (p_tmp // p)
    if M_tmp == 1: break

# create memo
## init
ip_max = max(ips)
memo = [[None] * N for i in range(ip_max + 1)] # max ip
for j in range(N): memo[0][j] = 1
for i in range(1, ip_max + 1): memo[i][N - 1] = 1
## fill
for i in range(1, ip_max + 1):
    sum_tmp = 1
    vals = list(memo[i - 1])[::-1]
    p_memo = memo[i]
    for j, val in enumerate(vals[1:]):
        sum_tmp += val
        p_memo[N - 2 - j] = sum_tmp

# calculate ans
ans = 1
for i_p in ips: ans = (ans * distribute(0, i_p, i_p)) % (10 ** 9 + 7) # oh...
    
print(ans)

Buggy submission (verdict: Runtime Error):
# encoding: utf-8
import math
N, M = map(int, input().split())

def distribute(pos, full, tmp):
    return memo[tmp][pos]

# define search range
p_max = int(M / 2) # M is prime if M has a factor p (> p_max)
ip_max = int(math.log2(M))

M_tmp = M
ips = []
for p in range(2, p_max + 1):
    # how many times M_tmp can be divided
    p_tmp = p
    for i_p in range(ip_max + 1):
        if M_tmp % p_tmp > 0: break
        p_tmp = p_tmp * p
    # escape if M_tmp cannot be divided
    if i_p < 1: continue
    # # ans update (dp)
    # ## expand memo if necessary
    # if i_p > ip_tmp:
    #     for i in range(ip_tmp + 1, i_p + 1):
    #         memo_tmp = [0] * N
    #         sum_tmp = 0 # memo[i - 1][N - 1]
    #         vals = list(memo[i - 1])[::-1]
    #         for j, val in enumerate(vals):
    #             sum_tmp += val
    #             memo_tmp[N - 1 - j] = sum_tmp
    #         memo[i] = list(memo_tmp)
    # ## search and count
    # ans_tmp = distribute(0, i_p, i_p)
    # ## add
    # ans = (ans * ans_tmp) % (10 ** 9 + 7)
    # calculate later
    ips.append(i_p)
    # next
    M_tmp = M_tmp // (p_tmp // p)
    if M_tmp == 1: break

# create memo
## init
ip_max = max(ips)
memo = [[None] * N for i in range(ip_max + 1)] # max ip
for j in range(N): memo[0][j] = 1
for i in range(1, ip_max + 1): memo[i][N - 1] = 1
## fill
for i in range(1, ip_max + 1):
    sum_tmp = 1
    vals = list(memo[i - 1])[::-1]
    p_memo = memo[i]
    for j, val in enumerate(vals[1:]):
        sum_tmp += val
        p_memo[N - 2 - j] = sum_tmp

# calculate ans
ans = 1
for i_p in ips: ans = (ans * distribute(0, i_p, i_p)) % (10 ** 9)

    
print(ans)

Buggy submission (verdict: Runtime Error):
# encoding: utf-8
import math
N, M = map(int, input().split())

def distribute(pos, full, tmp):
    # read memo
    if memo[pos][tmp] != None: return memo[pos][tmp]
    # end
    if tmp == 0: return 1
    # next
    ret = 0
    if pos < N - 1:
        for i in range(tmp + 1): ret += distribute(pos + 1, full, tmp - i)
    else: ret += 1
    # print("###", pos, tmp, ret)
    # write memo
    if memo[pos][tmp] != None: memo[pos][tmp] = ret
    return ret

# define search range
p_max = int(M / 2) # M is prime if M has a factor p (> p_max)
ip_max = int(math.log2(M))
memo = [[None] * (ip_max + 1) for i in range(N)] # max ip

M_tmp = M
ans = 1
for p in range(2, p_max + 1):
    # how many times M_tmp can be divided
    p_tmp = p
    for i_p in range(ip_max + 1):
        if M_tmp % p_tmp > 0: break
        p_tmp = p_tmp * p
    # escape if M_tmp cannot be divided
    if i_p < 1: continue
    # ans update (dp)
    ## search and count
    ans_tmp = distribute(0, i_p, i_p)
    ## add
    ans = (ans * ans_tmp) % (10 ** 9 + 7)
    # next
    M_tmp = M_tmp // (p_tmp // p)
    if M_tmp == 1: break

print(ans)

Buggy submission (verdict: Runtime Error):
# encoding: utf-8
import math
N, M = map(int, input().split())


def distribute(pos, full, tmp):
    # read memo
    if memo[pos][tmp] != None: return memo[pos][tmp]
    # end
    if tmp == 0: return 1
    # next
    ret = 0
    if pos < N - 1:
        for i in range(tmp + 1): ret += distribute(pos + 1, full, tmp - i)
    else: ret += 1
    # print("###", pos, tmp, ret)
    # write memo
    if memo[pos][tmp] != None: memo[pos][tmp] = ret
    return ret

# define search range
p_max = int(math.sqrt(M)) + 1
ip_max = int(math.log2(p_max))
memo = [[None] * (ip_max + 1) for i in range(N)] # max ip

M_tmp = M
ans = 1
for p in range(2, p_max + 1):
    # how many times M_tmp can be divided
    p_tmp = p
    for i_p in range(ip_max + 1):
        if M_tmp % p_tmp > 0: break
        p_tmp = p_tmp * p
    # escape if M_tmp cannot be divided
    if i_p < 1: continue
    # ans update (dp)
    ## search and count
    ans_tmp = distribute(0, i_p, i_p)
    ## add
    ans = (ans * ans_tmp) % (10 ** 9 + 7)
    # next
    M_tmp = M_tmp // (p_tmp // p)
    if M_tmp == 1: break

print(ans)

Buggy submission (verdict: Runtime Error):
# encoding: utf-8
N, M = map(int, input().split())

# primes = [2, 3, 5, 7, 11, 13, 17]

# M_tmp = M
# factors = []
# for p in primes:
#     for i_p in range(32):
#         if M_tmp % (p ** (i_p + 1)) > 0: break
#     if i_p > 0: factors.append((p, i_p))
#     M_tmp = M_tmp // (p ** i_p)

## memo
memo = [[None] * 33 for i in range(N)] # max ip

def distribute(pos, full, tmp):
    # read memo
    if memo[pos][tmp] != None: return memo[pos][tmp]
    # end
    if tmp == 0: return 1
    # next
    ret = 0
    if pos < N - 1:
        for i in range(tmp + 1): ret += distribute(pos + 1, full, tmp - i)
    else: ret += 1
    # print("###", pos, tmp, ret)
    # write memo
    if memo[pos][tmp] != None: memo[pos][tmp] = ret
    return ret

# ans = 1
# for p, i_p in factors:
#     tmp = distribute(0, i_p, i_p)
#     ans = ans * tmp
#     # print("#", p, tmp)

M_tmp = M
ans = 1
for p in range(2, 2 ** 32):
    # how many times M_tmp can be divided
    for i_p in range(33):
        if M_tmp % (p ** (i_p + 1)) > 0: break
    # escape if M_tmp cannot be divided
    # print("#", p, i_p)
    if i_p < 1: continue
    # ans update (dp)
    ## search and count
    ans_tmp = distribute(0, i_p, i_p)
    # print("###", ans_tmp)
    ## add
    ans = (ans * ans_tmp) % (10 ** 9 + 7)
    # next
    M_tmp = M_tmp // (p ** i_p)
    if M_tmp == 1: break # oh...

print(ans)

Buggy submission (verdict: Runtime Error):
# encoding: utf-8
N, M = map(int, input().split())

# primes = [2, 3, 5, 7, 11, 13, 17]

# M_tmp = M
# factors = []
# for p in primes:
#     for i_p in range(32):
#         if M_tmp % (p ** (i_p + 1)) > 0: break
#     if i_p > 0: factors.append((p, i_p))
#     M_tmp = M_tmp // (p ** i_p)

## memo
memo = [[None] * 33 for i in range(N)] # max ip

def distribute(pos, full, tmp):
    # read memo
    if memo[pos][tmp] != None: return memo[pos][tmp]
    # end
    if tmp == 0: return 1
    # next
    ret = 0
    if pos < N - 1:
        for i in range(tmp + 1): ret += distribute(pos + 1, full, tmp - i)
    else: ret += 1
    # print("###", pos, tmp, ret)
    # write memo
    if memo[pos][tmp] != None: memo[pos][tmp] = ret
    return ret

# ans = 1
# for p, i_p in factors:
#     tmp = distribute(0, i_p, i_p)
#     ans = ans * tmp
#     # print("#", p, tmp)

M_tmp = M
ans = 1
for p in range(2, 2 ** 32):
    # how many times M_tmp can be divided
    for i_p in range(33):
        if M_tmp % (p ** (i_p + 1)) > 0: break
    # escape if M_tmp cannot be divided
    # print("#", p, i_p)
    if i_p < 1: continue
    # ans update (dp)
    ## search and count
    ans_tmp = distribute(0, i_p, i_p)
    # print("###", ans_tmp)
    ## add
    ans = (ans * ans_tmp) % (10 ** 9 + 7)
    # next
    M_tmp = M_tmp // (p ** i_p)

print(ans)

Buggy submission (verdict: Runtime Error):
# encoding: utf-8
N, M = map(int, input().split())

# primes = [2, 3, 5, 7, 11, 13, 17]

# M_tmp = M
# factors = []
# for p in primes:
#     for i_p in range(32):
#         if M_tmp % (p ** (i_p + 1)) > 0: break
#     if i_p > 0: factors.append((p, i_p))
#     M_tmp = M_tmp // (p ** i_p)

## memo
memo = [[None] * 33 for i in range(N)] # max ip

def distribute(pos, full, tmp):
    # read memo
    if memo[pos][tmp] != None: return memo[pos][tmp]
    # end
    if tmp == 0: return 1
    # next
    ret = 0
    if pos < N - 1:
        for i in range(tmp + 1): ret += distribute(pos + 1, full, tmp - i)
    else: ret += 1
    # print("###", pos, tmp, ret)
    # write memo
    if memo[pos][tmp] != None: memo[pos][tmp] = ret
    return ret

# ans = 1
# for p, i_p in factors:
#     tmp = distribute(0, i_p, i_p)
#     ans = ans * tmp
#     # print("#", p, tmp)

M_tmp = M
ans = 1
for p in range(2, 4):
    # how many times M_tmp can be divided
    for i_p in range(33):
        if M_tmp % (p ** (i_p + 1)) > 0: break
    # escape if M_tmp cannot be divided
    # print("#", p, i_p)
    if i_p < 1: continue
    # ans update (dp)
    ## search and count
    ans_tmp = distribute(0, i_p, i_p)
    # print("###", ans_tmp)
    ## add
    ans = (ans * ans_tmp) % (10 ** 9 + 7)
    # next
    M_tmp = M_tmp // (p ** i_p)

print(ans)