Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
mod = 998244353

n, s = map(int, input().split())
a = list(map(int, input().split()))

a.sort()

while a[-1] > s:
    a.pop(-1)
    if a == []:
        print(0)
        exit()

dp = [0] * (s + 1)
dp[0] = 1
for i in a:
    newdp = [2 * j % mod for j in dp]
    for j in range(s - i + 1):
        newdp[j+i] += dp[j]
    dp = newdp

print(dp[s] * pow(2, n - len(a), mod) % mod)

Fixed submission:
mod = 998244353

n, s = map(int, input().split())
a = list(map(int, input().split()))

a.sort()

while a[-1] > s:
    a.pop(-1)
    if a == []:
        print(0)
        exit()

su = sum(a)
if su < s:
    print(0)
    exit()
if su == s:
    print(pow(2, n - len(a), mod))
    exit()

dp = [0] * (s + 1)
dp[0] = 1
for i in a:
    newdp = [2 * j for j in dp]
    for j in range(s - i + 1):
        newdp[j+i] += dp[j]
    dp = newdp

print(dp[s] * pow(2, n - len(a), mod) % mod)
Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
l = [0 for _ in range(k)]
for i in range(1, k):
    j = pow(k//i, n, 10**9+7)
    while i < k:
        i += i
        j -= l[i-1]
    l[i-1] = j
ans = sum(l) % (10**9+7)

Fixed submission:
n, k = map(int, input().split())
l = [0 for _ in range(k)]
for i in range(k-1, -1, -1):
    j = pow(k//(i+1), n, 10**9+7)
    for m in range(2, k//(i+1) + 1):
        j -= l[(i+1)*(m)-1]
    l[i] = j

ans = 0
for i in range(k):
    ans += (i+1) * l[i]
print(ans % (10**9+7))

Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
l = [0 for _ range(k)]
for i in range(1, k):
    j = pow(k//i, n, 10**9+7)
    while i < k:
        i += i
        j -= l[i-1]
    l[i-1] = j
ans = sum(l) % (10**9+7)

Fixed submission:
n, k = map(int, input().split())
l = [0 for _ in range(k)]
for i in range(k-1, -1, -1):
    j = pow(k//(i+1), n, 10**9+7)
    for m in range(2, k//(i+1) + 1):
        j -= l[(i+1)*(m)-1]
    l[i] = j

ans = 0
for i in range(k):
    ans += (i+1) * l[i]
print(ans % (10**9+7))
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int, input().split()))

inf = float('inf')

# 累積和
if n % 2 == 0:
  	while True:
      pass
    l_even = [0]
    l_odd = [0]
    for i in range(n):
        if i % 2 == 0:
            l_even.append(l_even[-1] + a[i])
        else:
            l_odd.append(l_odd[-1] + a[i])
    ans = -inf
    for i in range(n // 2 + 1):
        if ans < l_even[i] + l_odd[-1] - l_odd[i]:
            ans = l_even[i] + l_odd[-1] - l_odd[i]
    print(ans)
    exit()

# dp[i] = i回ずらしを使った時の最大値
# 1個ずつdpを更新
# i = 0, 1, 2
dp = [a[0], a[1], a[2]]
for i in range(2, n, 2):
    try:
        dp[2] = max([dp[2] + a[i+2], dp[1] + a[i+2]])
    except:
        pass
    try:
        dp[1] = max([dp[1] + a[i+1], dp[0] + a[i+1]])
    except:
        pass
    dp[0] += a[i]

print(max(dp))

Fixed submission:
n = int(input())
a = list(map(int, input().split()))

inf = float('inf')

# 累積和
if n % 2 == 0:
    l_even = [0]
    l_odd = [0]
    for i in range(n):
        if i % 2 == 0:
            l_even.append(l_even[-1] + a[i])
        else:
            l_odd.append(l_odd[-1] + a[i])
    ans = -inf
    for i in range(n // 2 + 1):
        if ans < l_even[i] + l_odd[-1] - l_odd[i]:
            ans = l_even[i] + l_odd[-1] - l_odd[i]
    print(ans)
    exit()

# dp[i] = i回ずらしを使った時の最大値
# 1個ずつdpを更新
# i = 0, 1, 2
dp = [a[0], a[1], a[2]]
for i in range(2, n-2, 2):
    dp[2] = max([dp[2] + a[i+2], dp[1] + a[i+2]])
    dp[1] = max([dp[1] + a[i+1], dp[0] + a[i+1]])
    dp[0] += a[i]

print(max(dp))
Buggy python submission (verdict: Runtime Error):
k = int(input())
l = ['1','2','3','4','5','6','7','8','9']
lf = ['1','2','3','4','5','6','7','8','9']
sum = 9
while sum < k:
    lff = []
    for i in lf:
        if i[-1] == [0]:
            lff.append(i+'0')
            lff.append(i+'1')
        elif i[-1] == [9]:
            lff.append(i+'8')
            lff.append(i+'9')
        else:
            lff.append(i+str(int(i[-1]-1)))
            lff.append(i+str(int(i[-1])))
            lff.append(i+str(int(i[-1]+1)))
    lf = lff
    l += lff
print(l[k-1])

Fixed submission:
k = int(input())
l = ['1','2','3','4','5','6','7','8','9']
lf = ['1','2','3','4','5','6','7','8','9']
sum = 9
while sum < k:
    lff = []
    for i in lf:
        if i[-1] == '0':
            lff.append(i+'0')
            lff.append(i+'1')
        elif i[-1] == '9':
            lff.append(i+'8')
            lff.append(i+'9')
        else:
            lff.append(i+str(int(i[-1])-1))
            lff.append(i+str(int(i[-1])))
            lff.append(i+str(int(i[-1])+1))
    lf = lff
    l += lff
    sum += len(lff)
print(int(l[k-1]))
Buggy python submission (verdict: Runtime Error):
n = int(input())

# n % k = 1 の数
m = n - 1
i = 2
ans = 1
while i * i <= m:
    if m % i == 0:
        num = 1
        while m % i == 0:
            num += 1
            m //= i
        ans *= num
    i = i + 1
if m != 1:
    ans *= 2
ans -= 1

# n % k = 0 の場合
# nを素因数分解する
m = n
import numpy as np
i = 2
factor = []
while i * i <= n:
    if n % i == 0:
        l = []
        num = 1
        l.append(num)
        while n % i == 0:
            num *= i
            l.append(num)
            n //= i
        factor.append(np.array(l))
    i = i + 1
if n > 1:
    factor.append(np.array([1, n]))

# 直積を求めることでnの全約数を得る
divisor = factor[-1]
for i in range(len(factor) - 1):
    divisor = np.outer(divisor, factor[i])
divisor = np.outer(np.array(1), divisor)

# 判定
for i in divisor[0]:
    if i == 1:
        continue
    n = m
    while n % i == 0:
        n //= i
    if n % i == 1:
        ans += 1

print(ans)

Fixed submission:
n = int(input())

# 例外処理
if n == 2:
    print(1)
    exit()
if n == 3:
    print(2)
    exit()

# n % k = 1 の数
m = n - 1
i = 2
ans = 1
while i * i <= m:
    if m % i == 0:
        num = 1
        while m % i == 0:
            num += 1
            m //= i
        ans *= num
    i = i + 1
if m != 1:
    ans *= 2
ans -= 1

# n % k = 0 の場合
# nを素因数分解する
m = n
import numpy as np
i = 2
factor = []
while i * i <= n:
    if n % i == 0:
        l = []
        num = 1
        l.append(num)
        while n % i == 0:
            num *= i
            l.append(num)
            n //= i
        factor.append(np.array(l))
    i = i + 1
if n > 1:
    factor.append(np.array([1, n]))

# 直積を求めることでnの全約数を得る
divisor = factor[-1]
for i in range(len(factor) - 1):
    divisor = np.outer(divisor, factor[i])
divisor = np.outer(np.array(1), divisor)

# 判定
for i in divisor[0]:
    if i == 1:
        continue
    n = m
    while n % i == 0:
        n //= i
    if n % i == 1:
        ans += 1

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, x, y = map(int, input().split())
lis = []
for i in range(1, n):
    for j in range(i+1, n+1):
        lis.append(min([j-i, abs(x-i)+1+abs(y-j), abs(y-i)+1+abs(x-j)]))
for i in range(1, n):
    print(lis.count(i))

Fixed submission:
n, x, y = map(int, input().split())
lis = [0]*(n-1)
for i in range(1, n):
    for j in range(i+1, n+1):
        lis[min([j-i, abs(x-i)+1+abs(y-j), abs(y-i)+1+abs(x-j)])-1] += 1
for i in range(n-1):
    print(lis[i])

Buggy python submission (verdict: Time Limit Exceeded):
#未提出
n, x, y = map(int, input().split())
lis = []
for i in range(1, n):
    for j in range(i+1, n+1):
        lis.append(min([j-i, abs(x-i)+1+abs(y-j), abs(y-i)+1+abs(x-j)]))
import collections
dic = collections.Counter(lis)
for i in range(1, n):
    print(dic[i])

Fixed submission:
n, x, y = map(int, input().split())
lis = [0]*(n-1)
for i in range(1, n):
    for j in range(i+1, n+1):
        lis[min([j-i, abs(x-i)+1+abs(y-j), abs(y-i)+1+abs(x-j)])-1] += 1
for i in range(n-1):
    print(lis[i])
Buggy python submission (verdict: Runtime Error):
N = int(input())

input_1 = input()
input_2 = input_1.split()

for k in range(N):
    A = map(int, input_2)

    def equal(num):
        return num / 1
    A = [equal(x) for x in A]

    ans = 0

    A.remove(A[k])

    for l in range(N - 1):
        for m in range(N - 1):
            if A[l] == A[m]:
                ans += 1
        
        ans -= 1

    ans = ans / 2

    print(int(ans))


Fixed submission:
N, M = map(int, input().split())

ans = (N * (N - 1) + M * (M - 1)) / 2

print(int(ans))

Buggy python submission (verdict: Runtime Error):
N = int(input())

input_1 = input()
input_2 = input_1.split()

A = map(int, input_2)

def equal(num):
    return num
A = [equal(x) for x in A]

ans = 0

for l in range(N):
    ans += A.count(A[l]) - 1

ans = ans / 2
re = ans

for k in range(N):
    ans -= A.count(A[k]) - 1

    print(int(ans))

    ans = re

Fixed submission:
N, M = map(int, input().split())

ans = (N * (N - 1) + M * (M - 1)) / 2

print(int(ans))
Buggy python submission (verdict: Time Limit Exceeded):
h, w, k = map(int, input().split())
s = []
for _ in range(h):
    s.append(list(map(int, list(input()))))

def vertical_line(h, w, k, s):
    ans = 0
    mark = [0 for _ in range(h)]
    for i in range(w):
        for j in range(h):
            mark[j] += s[j][i]
            if mark[j] > k:
                ans += 1
                mark = [s[l][i] for l in range(h)]
                break
    return ans

from copy import deepcopy
ans = []
for i in range(2 ** (h - 1)):
    s_copy = deepcopy(s)
    flag = False
    h_copy = h
    for j in range(h - 2, -1, -1):
        if i % 2 == 1:
            h_copy -= 1
            for l in range(w):
                s_copy[j][l] += s_copy[j+1][l]

                if s_copy[j][l] > k:
                    flag = True
                    break

            del s_copy[j+1]

        if flag:
            break

        i //= 2

    if flag:
        continue

    ans.append(h_copy - 1 + vertical_line(h_copy, w, k, s_copy))
print(min(ans))

Fixed submission:
h, w, k = map(int, input().split())
s = []
for _ in range(h):
    s.append(list(map(int, list(input()))))

def vertical_line(h, w, k, s):
    ans = 0
    mark = [0 for _ in range(h)]
    for i in range(w):
        for j in range(h):
            mark[j] += s[j][i]
            if mark[j] > k:
                ans += 1
                mark = [s[l][i] for l in range(h)]
                break
    return ans

from copy import deepcopy
ans = []
for i in range(2 ** (h - 1)):
    s_copy = deepcopy(s)
    flag = False
    h_copy = h
    for j in range(h - 2, -1, -1):
        if i % 2 == 1:
            h_copy -= 1
            for l in range(w):
                s_copy[j][l] += s_copy[j+1][l]

                if s_copy[j][l] > k:
                    flag = True
                    break

            del s_copy[j+1]

        if flag:
            break

        i //= 2

    if flag:
        continue

    ans.append(h_copy - 1 + vertical_line(h_copy, w, k, s_copy))
print(min(ans))
Buggy python submission (verdict: Runtime Error):
import sys
s = sys.stdin.readline().rstrip()
q = int(sys.stdin.readline().rstrip())

for _ in range(q):
    t = sys.stdin.readline().rstrip()
    if t == '1':
        s = s[::-1]
    else:
        t, f, c = t.split()
        if f == '1':
            s = c + s
        else:
            s = s + c

print(s)

Fixed submission:
s = input()
if s == 'AAA' or s == 'BBB':
    print('No')
else:
    print('Yes')
Buggy python submission (verdict: Runtime Error):
h, n = map(int, input().split())
a, b = [], []
for _ in range(n):
    i, j = map(int, input().split())
    a.append(i)
    b.append(j)

# DP
l = [0]
for i in range(1,h+1):
    cand = []
    for j in range(n):
        if i - a[j] >= 0 and l[i - a[j]] != 'none':
            cand.append(l[i - a[j]] + b[j])
    if cand == []:
        l.append('none')
    else:
        l.append(min(cand))
for i in range(h+1, h+max(a)):
    cand = []
    for j in range(n):
        if 0 <= i - a[j] < h and l[i - a[j]] != 'none':
            cand.append(l[i - a[j]] + b[j])
    if cand == []:
        l.append('none')
    else:
        l.append(min(cand))
l = l[h:]
l = [i for i in l if type(i) == int]
print(min(l))

Fixed submission:
h, a = map(int, input().split())
if h % a == 0:
    print(h//a)
else:
    print(h//a + 1)
Buggy python submission (verdict: Time Limit Exceeded):
h, n = map(int, input().split())
a, b = [], []
for _ in range(n):
    i, j = map(int, input().split())
    a.append(i)
    b.append(j)

# DP
l = [0]
for i in range(1,h+1):
    cand = []
    for j in range(n):
        if i - a[j] >= 0 and l[i - a[j]] != 'none':
            cand.append(l[i - a[j]] + b[j])
    if cand == []:
        l.append('none')
    else:
        l.append(min(cand))
for i in range(h+1, h+max(a)):
    cand = []
    for j in range(n):
        if 0 <= i - a[j] < h and l[i - a[j]] != 'none':
            cand.append(l[i - a[j]] + b[j])
    if cand == []:
        l.append('none')
    else:
        l.append(min(cand))
l = l[h:]
l = [i for i in l if type(i) == int]
print(min(l))

Fixed submission:
h, n = map(int, input().split())
a, b = [], []
for _ in range(n):
    i, j = map(int, input().split())
    a.append(i)
    b.append(j)

# DP
l = [0]
for i in range(1,h+1):
    cand = []
    for j in range(n):
        if i - a[j] >= 0 and l[i - a[j]] != 'none':
            cand.append(l[i - a[j]] + b[j])
    if cand == []:
        l.append('none')
    else:
        l.append(min(cand))
for i in range(h+1, h+max(a)):
    cand = []
    for j in range(n):
        if 0 <= i - a[j] < h and l[i - a[j]] != 'none':
            cand.append(l[i - a[j]] + b[j])
    if cand == []:
        l.append('none')
    else:
        l.append(min(cand))
l = l[h:]
l = [i for i in l if type(i) == int]
print(min(l))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))

lcm = 1
from fractions import gcd
for i in range(n):
    lcm *= a[i] // gcd(a[i], lcm)

ans = 0
for i in a:
    ans += lcm // i

print(ans % (10**9+7))

Fixed submission:
n = int(input())
a = list(map(int, input().split()))

lcm = 1
from fractions import gcd
for i in range(n):
    lcm *= a[i] // gcd(a[i], lcm)

ans = 0
for i in a:
    ans += lcm // i

print(ans % (10**9+7))

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))

lcm = 1
from fractions import gcd
for i in range(n):
    lcm *= a[i] // gcd(a[i], lcm)

ans = 0
for i in a:
    ans += lcm // i

print(ans % (10**9+7))

Fixed submission:
n = int(input())
a = list(map(int, input().split()))

lcm = 1
from fractions import gcd
for i in range(n):
    lcm *= a[i] // gcd(a[i], lcm)

ans = 0
for i in a:
    ans += lcm // i

print(ans % (10**9+7))

Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int, input().split()))

lcm = 1
from math import gcd
for i in range(n):
    lcm *= a[i] // gcd(a[i], lcm)

ans = 0
for i in a:
    ans += lcm // i

print(ans % (10**9+7))

Fixed submission:
n = int(input())
a = list(map(int, input().split()))

lcm = 1
from fractions import gcd
for i in range(n):
    lcm *= a[i] // gcd(a[i], lcm)

ans = 0
for i in a:
    ans += lcm // i

print(ans % (10**9+7))
Buggy python submission (verdict: Runtime Error):
h, w = map(int, input().split())
s = [['#' for _ in range(w+2)]]
for _ in range(h):
    s.append(list('#' + input() + '#'))
s.append(['#' for _ in range(w+2)])

# WFS
ans = []
d = [(1,0), (0,1), (-1,0), (0,-1)]
from collections import deque
for i in range(1, h+1):
    for j in (1, w+1):
        if s[i][j] == '#':
            continue
        seen = [[-1 for _ in range(w+2)] for __ in range(h+2)]
        seen[i][j] = 0
        todo = deque([(i, j)])
        num = 0
        while todo != deque([]):
            x, y = todo.popleft()
            for k in d:
                xk = x + k[0]
                yk = y + k[1]
                if seen[xk][yk] == -1 and s[xk][yk] == '.':
                    num = seen[x][y] + 1
                    seen[xk][yk] = num
                    todo.append((xk,yk))
        ans.append(num)
print(max(ans))

Fixed submission:
h, w = map(int, input().split())
s = [['#' for _ in range(w+2)]]
for _ in range(h):
    s.append(list('#' + input() + '#'))
s.append(['#' for _ in range(w+2)])

# WFS
ans = []
d = [(1,0), (0,1), (-1,0), (0,-1)]
from collections import deque
for i in range(1, h+1):
    for j in range(1, w+1): # start = s[i][j]
        if s[i][j] == '#':
            continue
        seen = [[-1 for _ in range(w+2)] for __ in range(h+2)]
        seen[i][j] = 0
        todo = deque([(i, j)])
        num = 0
        while todo != deque([]):
            x, y = todo.popleft()
            for k in d:
                xk = x + k[0]
                yk = y + k[1]
                if seen[xk][yk] == -1 and s[xk][yk] == '.':
                    num = seen[x][y] + 1
                    seen[xk][yk] = num
                    todo.append((xk,yk))
        ans.append(num)
print(max(ans))
Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())
a = list(map(int, input().split()))

num1 = a[0]
num2 = 0
while num1 % 2 == 0:
    num1 //= 2
    num2 += 1
gc = 2 ** num2

b = []
for i in a:
    if i % gc != 0 or (i // gc) % 2 == 0:
        print(0)
        exit()
    else:
        b.append(i // gc)

from math import gcd
lcm = 1
for i in b:
    lcm = (lcm * i) // gcd(lcm, i)

ans = m // (lcm * (gc // 2))
ans = (ans + 1) // 2
print(ans)

Fixed submission:
n, m = map(int, input().split())
a = list(map(int, input().split()))

num1 = a[0]
num2 = 0
while num1 % 2 == 0:
    num1 //= 2
    num2 += 1
gc = 2 ** num2

b = []
for i in a:
    if i % gc != 0 or (i // gc) % 2 == 0:
        print(0)
        exit()
    else:
        b.append(i // gc)

from fractions import gcd
lcm = 1
for i in b:
    lcm = (lcm * i) // gcd(lcm, i)

ans = m // (lcm * (gc // 2))
ans = (ans + 1) // 2
print(ans)

Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())
a = list(map(int, input().split()))

num1 = a[0]
num2 = 0
while num1 % 2 == 0:
    num1 //= 2
    num2 += 1
gc = 2 ** num2

b = []
for i in a:
    if i % gc != 0 or (i // gc) % 2 == 0:
        print(0)
        exit()
    else:
        b.append(i // gc)

from math import gcd
lcm = 1
for i in b:
    lcm = (lcm * i) // gcd(lcm, i)

ans = m // lcm
if ans % 2 == 0:
    ans //= 2
else:
    ans = (ans + 1) // 2
print(ans)

Fixed submission:
n, m = map(int, input().split())
a = list(map(int, input().split()))

num1 = a[0]
num2 = 0
while num1 % 2 == 0:
    num1 //= 2
    num2 += 1
gc = 2 ** num2

b = []
for i in a:
    if i % gc != 0 or (i // gc) % 2 == 0:
        print(0)
        exit()
    else:
        b.append(i // gc)

from fractions import gcd
lcm = 1
for i in b:
    lcm = (lcm * i) // gcd(lcm, i)

ans = m // (lcm * (gc // 2))
ans = (ans + 1) // 2
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
mod = 1000000007
n = int(input())
a = list(map(int, input().split()))

lap = 0
big = max(a)
while big > 0:
    big //= 2
    lap += 1

xor = [0 for _ in range(lap)]
for i in a:
    num = 0
    for j in range(lap):
        if i % 2 == 1:
            xor[num] += 1
        i //= 2
        num += 1

ans = 0
for i in range(lap):
    ans += pow(2, i, mod) * xor[i] * (n - xor[i]) % mod
    ans %= mod

print(ans)

Fixed submission:
mod = 1000000007
n = int(input())
a = list(map(int, input().split()))

lap = 0
big = max(a)
while big > 0:
    big //= 2
    lap += 1

xor = [0 for _ in range(lap)]
for i in a:
    num = 0
    for j in range(lap):
        if i % 2 == 1:
            xor[num] += 1
        i //= 2
        num += 1

ans = 0
for i in range(lap):
    ans += pow(2, i, mod) * xor[i] * (n - xor[i]) % mod
    ans %= mod

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from sys import setrecursionlimit
setrecursionlimit(10**8)

def main():
    n = int(input())
    a = list(map(int, input().split()))

    dp = [[[-1] * (n+1) for _ in range(n+1)] for _ in range(n+1)]
    dp[0][0][0] = 0.0

    def search(i, j, k):
        if dp[i][j][k] != -1:
            return dp[i][j][k]

        num = n
        if i > 0:
            num += search(i-1, j, k) * i
        if j > 0:
            num += search(i+1, j-1, k) * j
        if k > 0:
            num += search(i, j+1, k-1) * k
        num /= i + j + k

        dp[i][j][k] = num
        return num

    print(search(a.count(1), a.count(2), a.count(3)))

main()

Fixed submission:
from sys import setrecursionlimit
setrecursionlimit(10**8)

def main():
    n = int(input())
    a = list(map(int, input().split()))

    dp = [[[-1] * (n+1) for _ in range(n+1)] for _ in range(n+1)]
    dp[0][0][0] = 0.0

    def search(i, j, k):
        num = n
        if i > 0:
            if dp[i-1][j][k] == -1:
                num += search(i-1, j, k) * i
            else:
                num += dp[i-1][j][k] * i
        if j > 0:
            if dp[i+1][j-1][k] == -1:
                num += search(i+1, j-1, k) * j
            else:
                num += dp[i+1][j-1][k] * j
        if k > 0:
            if dp[i][j+1][k-1] == -1:
                num += search(i, j+1, k-1) * k
            else:
                num += dp[i][j+1][k-1] * k
        num /= i + j + k

        dp[i][j][k] = num
        return num

    print(search(a.count(1), a.count(2), a.count(3)))

main()
Buggy python submission (verdict: Runtime Error):
class Factorials:
    def __init__(self, n=10**6, mod=10**9 + 7):
        self.mod = mod

        # self.fac[i] ≡ i! (factorial:階乗)
        self.fac = [1]
        num = 1
        for i in range(1, n+1):
            num *= i
            num %= mod
            self.fac.append(num)

        # self.rec[i] ≡ 1 / i! (reciprocal:逆数)
        num = pow(num, mod-2, mod)
        self.rec = [1 for i in range(n+1)]
        self.rec[n] = num
        for i in range(n-1, 0, -1):
            num *= i + 1
            num %= mod
            self.rec[i] = num

    # comb(n, r) ≡ nCr
    def comb(self, n, r):
        return self.fac[n] * self.rec[r] * self.rec[n - r] % self.mod
    
    # perm(n, r) ≡ nPr
    def perm(self, n, r):
        return self.fac[n] * self.rec[n-r] % self.mod

    # fact(n) ≡ n!
    def fact(self, n):
        return self.fac[n]

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

    factors = []
    for i in range(2, m+1):
        if i * i > m:
            if m > 1:
                factors.append(1)
            break

        if m % i == 0:
            num = 1
            m //= i
            while m % i == 0:
                num += 1
                m //= i
            factors.append(num)

    fct = Factorials(n=n+max(factors), mod=mod)

    ans = 1
    for i in factors:
        ans *= fct.comb(n+i-1, i)
        ans %= mod

    print(ans)

main()

Fixed submission:
class Factorials:
    def __init__(self, n=10**6, mod=10**9 + 7):
        self.mod = mod

        # self.fac[i] ≡ i! (factorial:階乗)
        self.fac = [1]
        num = 1
        for i in range(1, n+1):
            num *= i
            num %= mod
            self.fac.append(num)

        # self.rec[i] ≡ 1 / i! (reciprocal:逆数)
        num = pow(num, mod-2, mod)
        self.rec = [1 for i in range(n+1)]
        self.rec[n] = num
        for i in range(n-1, 0, -1):
            num *= i + 1
            num %= mod
            self.rec[i] = num

    # comb(n, r) ≡ nCr
    def comb(self, n, r):
        return self.fac[n] * self.rec[r] * self.rec[n - r] % self.mod
    
    # perm(n, r) ≡ nPr
    def perm(self, n, r):
        return self.fac[n] * self.rec[n-r] % self.mod

    # fact(n) ≡ n!
    def fact(self, n):
        return self.fac[n]

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

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

    factors = []
    for i in range(2, m+1):
        if i * i > m:
            if m > 1:
                factors.append(1)
            break

        if m % i == 0:
            num = 1
            m //= i
            while m % i == 0:
                num += 1
                m //= i
            factors.append(num)

    fct = Factorials(n=n+max(factors), mod=mod)

    ans = 1
    for i in factors:
        ans *= fct.comb(n+i-1, i)
        ans %= mod

    print(ans)

main()