Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
str = input()
length = len(str)
ans = [""] * length
for x in range(length):
    if str[length - (x + 1)] == "P":ans[length - (x + 1)] += "P"
    elif str[length - (x + 1)] == "D":ans[length - (x + 1)] += "D"
    elif str[length - (x + 1)] == "?":
        if x == 0 or x == length: ans[length - (x + 1)] = "D"
        elif ans[length - x] == "P": ans[length - (x + 1)] = "D"
        elif ans[length - x] == "D" and ans[length - (x - 1)] == "P": ans[length - (x + 1)] = "D"
        elif ans[length - x] == "D" and ans[length - (x - 1)] == "D": ans[length - (x + 1)] = "P"
print(''.join(ans))

Fixed submission:
str = input()
length = len(str)
ans = [""] * length
for x in range(length):
    if str[length - (x + 1)] == "P":ans[length - (x + 1)] += "P"
    elif str[length - (x + 1)] == "D":ans[length - (x + 1)] += "D"
    elif str[length - (x + 1)] == "?":
        if x == 0 or x == length - 1: ans[length - (x + 1)] = "D"
        elif ans[length - x] == "P": ans[length - (x + 1)] = "D"
        elif ans[length - x] == "D" and str[length - (x + 2)] == "P": ans[length - (x + 1)] = "D"
        elif ans[length - x] == "D" and str[length - (x + 2)] == "D": ans[length - (x + 1)] = "P"
        elif ans[length - x] == "D" and str[length - (x + 2)] == "?": ans[length - (x + 1)] = "P"
print(''.join(ans))
Buggy python submission (verdict: Time Limit Exceeded):
num = int(input())
list = list(map(int, input().split()))
for x in range(num):
    print(list.count(x + 1))

Fixed submission:
num = int(input())
list = list(map(int, input().split()))
ans = [0] * (num + 1)
for x in list:
    ans[x] += 1
for x in range(num):
    print(ans[x + 1])
Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
mod = 10 ** 9 + 7
premin = 0
premax = 0
ans = 0
list = [i for i in range(n + 1)]
for x in range(n + 2):
    premin = sum(list[x])
    premax = sum(list[n + 1 - x])
    if x < k: continue
    ans += (premax - premin + 1)
    if ans >= mod: ans %= mod
print(ans)


Fixed submission:
n, k = map(int, input().split())
mod = 10 ** 9 + 7
premin = 0
premax = 0
ans = 0
list = [i for i in range(n + 1)]
for x in range(n + 1):
    premin += list[x]
    premax += list[n - x]
    if x < k - 1: continue
    ans += (premax - premin + 1)
    if ans >= mod: ans %= mod
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
mod = 10 ** 9 + 7
premin = 0
premax = 0
ans = 0
list = [i for i in range(n + 1)]
for x in range(n + 2):
    if x < k: continue
    premin = sum(list[0 : x])
    premax = sum(list[n + 1 - x : n + 1])
    ans += (premax - premin + 1)
    if ans >= mod: ans %= mod
print(ans)


Fixed submission:
n, k = map(int, input().split())
mod = 10 ** 9 + 7
premin = 0
premax = 0
ans = 0
list = [i for i in range(n + 1)]
for x in range(n + 1):
    premin += list[x]
    premax += list[n - x]
    if x < k - 1: continue
    ans += (premax - premin + 1)
    if ans >= mod: ans %= mod
print(ans)

Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
mod = 10 ** 9 + 7
premin = 0
premax = 0
ans = 0
list = [i for i in range(n + 1)]
for x in range(n + 2):
    if x < k: continue
    if k < x: ans += pre
    premin = sum(list[0 : x])
    premax = sum(list[n + 1 - x : n + 1])
    ans += (premax - premin + 1) % mod
print(ans)

Fixed submission:
n, k = map(int, input().split())
mod = 10 ** 9 + 7
premin = 0
premax = 0
ans = 0
list = [i for i in range(n + 1)]
for x in range(n + 1):
    premin += list[x]
    premax += list[n - x]
    if x < k - 1: continue
    ans += (premax - premin + 1)
    if ans >= mod: ans %= mod
print(ans)
Buggy python submission (verdict: Runtime Error):
str = input()
if str[0] == "7" or str[1] == "7" or str[2] == "7": print("Yes")
    print("No")

Fixed submission:
str = input()
if str[0] == "7" or str[1] == "7" or str[2] == "7": print("Yes")
else: print("No")
Buggy python submission (verdict: Runtime Error):
str = input()
if str[0] == "7" or str[1] == "7" or str[2] == "7": print("Yes")
else: print("No")

Fixed submission:
num = int(input())
ans = 0
for x in range(num + 1):
    if x % 3 == 0 or x % 5 == 0: pass
    else: ans += x
print(ans)
Buggy python submission (verdict: Runtime Error):
import math

num = int(input())
ans = 0
for a in num:
    for b in num:
        for c in num:
            ans += math.gcd(a, b, c)
print(ans)

Fixed submission:
import math

num = int(input())
ans = 0
for a in range(num):
    for b in range(num):
        temp = math.gcd(a + 1, b + 1)
        for c in range(num):
            ans += math.gcd(temp, c + 1)
print(ans)
Buggy python submission (verdict: Runtime Error):
x, y, z = map(int, input().split())
print(z + " " + x + " " + y)


Fixed submission:
x, y, z = map(str, input().split())
print(z + " " + x + " " + y)
Buggy python submission (verdict: Time Limit Exceeded):
num = int(input())
a_i = list(map(int, input().split()))
anslist = [0] * (num + 1)
for x in range(num):
    val = x + 1
    cnt = a_i.count(val)
    if cnt <= 1: anslist[val] = 0
    else: anslist[val] = cnt * (cnt - 1) // 2

ans = sum(anslist)
for x in range(num):
    val = a_i[x]
    cnt = a_i.count(val)
    if cnt <= 1: print(ans)
    else: 
        sa = (cnt - 1)
        print(ans - sa)
        

Fixed submission:
import collections

num = int(input())
a_i = list(map(int, input().split()))
anslist = collections.Counter(a_i)

ans = 0
for x in anslist.values():
    ans += x * (x - 1) // 2
for x in range(num):
    val = a_i[x]
    cnt = anslist[val]
    print(ans - (cnt - 1))

Buggy python submission (verdict: Time Limit Exceeded):
num = int(input())
a_i = list(map(int, input().split()))
anslist = [0] * (num + 1)
printlist = [0] * (num + 1)
for x in range(num):
    val = x + 1
    cnt = a_i.count(val)
    if cnt <= 1: anslist[val] = 0
    else: anslist[val] = cnt * (cnt - 1) // 2

ans = sum(anslist)
for x in range(num):
    val = a_i[x]
    cnt = a_i.count(val)
    if printlist[val] != 0: 
        print(printlist[val])
        continue
    if cnt <= 1: print(ans)
    else: 
        sa = anslist[val] - (cnt - 1) * (cnt - 2) // 2
        print(ans - sa)
        printlist[val] = ans - sa


Fixed submission:
import collections

num = int(input())
a_i = list(map(int, input().split()))
anslist = collections.Counter(a_i)

ans = 0
for x in anslist.values():
    ans += x * (x - 1) // 2
for x in range(num):
    val = a_i[x]
    cnt = anslist[val]
    print(ans - (cnt - 1))
Buggy python submission (verdict: Runtime Error):
h, w = map(int, input().split())
if h == 1 or w == 1: print(1)
else: print((h * w + 1) // 2)

Fixed submission:
a, b, c = map(int, input().split())
val = a * b
if c - a - b > 0 and 4 * a * b < (c - a - b) ** 2: print('Yes')
else: print('No')
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
p_i = list(map(int,input().split()))
answer = 0
for x in range(n - k + 1):
    answer = max(answer, sum(p_i[x : x + k]))
print((answer + k) / 2)

Fixed submission:
n, k = map(int, input().split())
p_i = list(map(int,input().split()))
answer = 0
sum = 0
for x in range(n):
    if x <= k - 1: 
        sum += p_i[x]
        if x == k - 1: answer = sum
    else:
        sum += p_i[x] - p_i[x - k]
        answer = max(answer, sum)
print((answer + k) / 2)

Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
p_i = input().split()
answer = 0
sumlist =[] 
for x in range(n - k + 1):
    sumlist = p_i[x : x + k]
    answer = max(answer, sum(int(i) for i in sumlist))
print((answer + k) / 2)

Fixed submission:
n, k = map(int, input().split())
p_i = list(map(int,input().split()))
answer = 0
sum = 0
for x in range(n):
    if x <= k - 1: 
        sum += p_i[x]
        if x == k - 1: answer = sum
    else:
        sum += p_i[x] - p_i[x - k]
        answer = max(answer, sum)
print((answer + k) / 2)

Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
p_i = input().split()
answer = 0
for x in range(n):
    if x <= k - 1:
        sum = 0
        for y in range(k):
            sum += int(p_i[x + y])
        answer = max(answer, sum)
print((answer + k) / 2)

Fixed submission:
n, k = map(int, input().split())
p_i = list(map(int,input().split()))
answer = 0
sum = 0
for x in range(n):
    if x <= k - 1: 
        sum += p_i[x]
        if x == k - 1: answer = sum
    else:
        sum += p_i[x] - p_i[x - k]
        answer = max(answer, sum)
print((answer + k) / 2)
Buggy python submission (verdict: Runtime Error):
a, b = map(int, input().split())
if b % a　== 0: print(a + b)
else: print(b - a)

Fixed submission:
a, b = map(int, input().split())
if b % a == 0: print(a + b)
else: print(b - a)
Buggy python submission (verdict: Runtime Error):
import math
n = int(input())
ans = 0
t_1, a_1 = map(int, input().split())
pret = t_1
prea = a_1
for x in range(n - 1):
    t, a = map(int, input().split())
    else:
        m = max(math.ceil(pret / t), math.ceil(prea / a))
        pret = m * t
        prea = m * a
print(pret + prea)

Fixed submission:
import math
n = int(input())
ans = 0
t_1, a_1 = map(int, input().split())
pret = t_1
prea = a_1
for x in range(n - 1):
    t, a = map(int, input().split())
    m = -min(-pret//t,-prea//a)
    pret = m * t
    prea = m * a
print(pret + prea)

Buggy python submission (verdict: Time Limit Exceeded):
import math
n = int(input())
ans = 0
pret = 0
prea = 0
for x in range(n):
    t, a = map(int, input().split())
    if ans == 0 : 
        ans = t + a 
        pret = t
        prea = a
    else:
        sum = t + a
        ans = math.ceil(ans / sum) * sum
        while (pret > (ans * t // sum) or prea > (ans * a // sum)):
            ans += sum
        pret = ans * t // sum
        prea = ans * a // sum
print(ans)

Fixed submission:
import math
n = int(input())
ans = 0
t_1, a_1 = map(int, input().split())
pret = t_1
prea = a_1
for x in range(n - 1):
    t, a = map(int, input().split())
    m = -min(-pret//t,-prea//a)
    pret = m * t
    prea = m * a
print(pret + prea)
Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
d_i = set(map(int, input().split()))
full = set(range(10))
useableList = full - d_i
useable_Top = full - d_i - set([0])
answer = []
isTop = True
for x in str(n):
    if int(x) in useableList: answer.append(x)
    elif isTop: answer.append(min(useable_Top - set(range(int(x) + 1))))
    else: answer.append(min(useableList))
    if isTop: isTop = False;
ans = ''
for x in range(len(answer)):
    ans += str(answer[x])
print(ans)

Fixed submission:
n, k = map(int, input().split())
d_k = set(map(int, input().split()))
ans = n
while ans <= n * 10:
    isOK = True
    for x in range(len(str(ans))):
        if int(str(ans)[x]) in d_k: 
            isOK = False
            break
    if isOK == True: break
    ans += 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N = int(input())
    X = int(input(), 2)

    def f(x):
        c = 0
        while x:
            c += 1
            x = x % bin(x).count('1')
        return c
    for i in range(N):
        print(f(X ^ (1 << (N - 1 - i))))


main()


Fixed submission:
def main():
    N = int(input())
    S = input()
    X = int(S, 2)
    C = S.count('1')
    xc0 = X % (C + 1)
    xc1 = X % (C - 1) if C > 1 else 0

    def f(x):
        c = 0
        while x:
            c += 1
            x = x % bin(x).count('1')
        return c

    for i, s in enumerate(S):
        k = N - 1 - i
        if s == '0':
            print(f((xc0 + pow(2, k, C + 1)) % (C + 1)) + 1)
        else:
            if C > 1:
                print(f((xc1 - pow(2, k, C - 1)) % (C - 1)) + 1)
            else:
                print(0)


main()
Buggy python submission (verdict: Runtime Error):
def main():
    N = int(input())
    E = [0] * N
    for _ in range(N - 1):
        u, v = map(int, input().split())
        u, v = u - 1, v - 1
        if u > v:
            u, v = v, u
        E[v] += 1
    t = 0
    U = [0] * N
    for i in range(N):
        t += E[i]
        U[i] = t

    t = n * (n + 1) * (n + 2 ) // 6
    for i in range(N):
        t += U[i] * i - U[i] * (N - i)
    return t

print(main())


Fixed submission:
def main():
    N = int(input())
    h = 0
    for _ in range(N - 1):
        u, v = map(int, input().split())
        if u > v:
            u, v = v, u
        h += u * (N + 1 - v)

    return N * (N + 1) * (N + 2) // 6 - h

print(main())
Buggy python submission (verdict: Time Limit Exceeded):
class nCrMod():
    def __init__(self, mod):
        self.mod = mod
        self.fac = [1, 1]
        self.finv = [1, 1]
        self.inv = [0, 1]

    def prep(self, n):
        mod = self.mod
        f, fi = self.fac[-1], self.finv[-1]
        for i in range(len(self.fac), n + 1):
            fn = f * i % mod
            v = -self.inv[mod % i] * (mod // i) % mod
            fin = fi * v % mod
            f, fi = fn, fin
            self.fac.append(f)
            self.finv.append(fi)
            self.inv.append(v)

    def __call__(self, n, r):
        if len(self.fac) <= n:
            self.prep(n)
        return self.fac[n] * self.finv[r] * self.finv[n - r] % self.mod


def main():
    K = int(input())
    S = input()
    N = len(S)
    mod = 10**9 + 7
    nCr = nCrMod(mod)
    r = 0
    for i in range(K + 1):
        r = (r + pow(25, i, mod) * pow(26, K - i, mod) * nCr(N + i - 1, N - 1)) % mod
    return r

        
print(main())


Fixed submission:
def main():
    K = int(input())
    S = input()
    N = len(S)
    mod = 10**9 + 7
    r = 0
    t = pow(26, K, mod)
    s = 1
    inv26 = pow(26, mod - 2, mod)
    inv = [0] * (K + 2)
    inv[1] = 1
    for i in range(2, K + 2):
        inv[i] = -inv[mod % i] * (mod // i) % mod
    for i in range(K + 1):
        r = (r + t * s) % mod
        t = (t * 25 * inv26) % mod
        s = (s * (N + i) * inv[i + 1]) % mod
    return r

        
print(main())

Buggy python submission (verdict: Time Limit Exceeded):
def solve(K, N):
    mod = 10**9 + 7
    T = [0] * (N + 1)
    T[0] = 1
    for i in range(K + N):
        T[N] = (T[N - 1] + T[N] * 26) % mod
        for j in reversed(range(1, N)):
            T[j] = (T[j - 1]  + T[j] * 25) % mod
        T[0] = (T[0] * 25) % mod
    return T[-1] % mod

def main():
    K = int(input())
    S = input()
    return solve(K, len(S))
        
print(main())


Fixed submission:
def main():
    K = int(input())
    S = input()
    N = len(S)
    mod = 10**9 + 7
    r = 0
    t = pow(26, K, mod)
    s = 1
    inv26 = pow(26, mod - 2, mod)
    inv = [0] * (K + 2)
    inv[1] = 1
    for i in range(2, K + 2):
        inv[i] = -inv[mod % i] * (mod // i) % mod
    for i in range(K + 1):
        r = (r + t * s) % mod
        t = (t * 25 * inv26) % mod
        s = (s * (N + i) * inv[i + 1]) % mod
    return r

        
print(main())
Buggy python submission (verdict: Runtime Error):
def main():
    X = int(input())

    for i in range(10**5):
        t += X
        if t % 360 == 0:
            return i + 1

print(main())


Fixed submission:
def main():
    X = int(input())
    t = 0

    for i in range(10**5):
        t += X
        if t % 360 == 0:
            return i + 1

print(main())
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    A, B, C, D = list(map(int, input().split()))
    mod = 998244353
    dp = [[0] * (D + 1) for _ in range(C + 1)]
    dp[A][B] = 1
    for b in range(B + 1, D + 1):
        dp[A][b] = dp[A][b - 1] * A
    for a in range(A + 1, C + 1):
        dp[a][B] = dp[a - 1][B] * B % mod
        for b in range(B + 1, D + 1):
            dp[a][b] = (dp[a - 1][b] * b + dp[a][b - 1] * a - dp[a - 1][b - 1] * (a - 1) * (b - 1)) % mod

    return dp[C][D]

print(main())


Fixed submission:
def main():
    A, B, C, D = list(map(int, input().split()))
    mod = 998244353
    u = [0] * (D + 1)
    v = [0] * (D + 1)
    u[B] = 1
    for b in range(B + 1, D + 1):
        u[b] = u[b - 1] * A
    for a in range(A + 1, C + 1):
        v[B] = u[B] * B % mod
        for b in range(B + 1, D + 1):
            v[b] = (u[b] * b + v[b - 1] * a - u[b - 1] * (a - 1) * (b - 1)) % mod
        u, v = v, u

    return u[D]

print(main())

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    A, B, C, D = list(map(int, input().split()))
    mod = 998244353
    dp = [[0] * (D + 1) for _ in range(C + 1)]
    dp[A][B] = 1
    for b in range(B + 1, D + 1):
        dp[A][b] = dp[A][b - 1] * A
    for a in range(A + 1, C + 1):
        dp[a][B] = dp[a - 1][B] * B % mod
        for b in range(B + 1, D + 1):
            dp[a][b] = (dp[a - 1][b] * b + dp[a][b - 1] * a - dp[a - 1][b - 1] * (a - 1) * (b - 1)) % mod

    return dp[C][D]

print(main())


Fixed submission:
def main():
    A, B, C, D = list(map(int, input().split()))
    mod = 998244353
    u = [0] * (D + 1)
    v = [0] * (D + 1)
    u[B] = 1
    for b in range(B + 1, D + 1):
        u[b] = u[b - 1] * A
    for a in range(A + 1, C + 1):
        v[B] = u[B] * B % mod
        for b in range(B + 1, D + 1):
            v[b] = (u[b] * b + v[b - 1] * a - u[b - 1] * (a - 1) * (b - 1)) % mod
        u, v = v, u

    return u[D]

print(main())
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    for _ in range(K):
        m = True
        a = [0] * N
        t = 0
        for i in range(N):
            t += a[i] + 1
            if i + A[i] + 1< N:
                a[i + A[i] + 1] -= 1
            a[i] = t
        t = 0
        b = [0] * N
        for i in reversed(range(N)):
            t += b[i]
            b[i] = t
            t += 1
            if i - A[i] - 1 >= 0:
                b[i - A[i] - 1] -= 1
            A[i] = a[i] + b[i]
            if a[i] < N:
                m = False
        if m:
            break
    return A

print(*main())


Fixed submission:
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    for _ in range(K):
        m = True
        a = [0] * N
        t = 0
        for i in range(N):
            t += a[i] + 1
            if i + A[i] + 1< N:
                a[i + A[i] + 1] -= 1
            a[i] = t
        t = 0
        b = [0] * N
        for i in reversed(range(N)):
            t += b[i]
            b[i] = t
            t += 1
            if i - A[i] - 1 >= 0:
                b[i - A[i] - 1] -= 1
            A[i] = a[i] + b[i]
            if A[i] < N:
                m = False
        if m:
            break
    return A

print(*main())

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    for _ in range(K):
        a = [0] * N
        t = 0
        for i in range(N):
            t += a[i] + 1
            if i + A[i] + 1< N:
                a[i + A[i] + 1] -= 1
            a[i] = t
        t = 0
        b = [0] * N
        for i in reversed(range(N)):
            t += b[i]
            b[i] = t
            t += 1
            if i - A[i] - 1 >= 0:
                b[i - A[i] - 1] -= 1
            A[i] = a[i] + b[i]
    return A

print(*main())


Fixed submission:
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    for _ in range(K):
        m = True
        a = [0] * N
        t = 0
        for i in range(N):
            t += a[i] + 1
            if i + A[i] + 1< N:
                a[i + A[i] + 1] -= 1
            a[i] = t
        t = 0
        b = [0] * N
        for i in reversed(range(N)):
            t += b[i]
            b[i] = t
            t += 1
            if i - A[i] - 1 >= 0:
                b[i - A[i] - 1] -= 1
            A[i] = a[i] + b[i]
            if A[i] < N:
                m = False
        if m:
            break
    return A

print(*main())
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    T = int(input())
    for _ in range(T):
        N = int(input())
        A = list(map(int, input().split()))
        S = input()
        cur = set([0])
        for a, s in zip(reversed(A), reversed(S)):
            if s == '1':
                nxt = set()
                for o in cur:
                    if o ^ a in cur:
                        nxt.add(o)
                cur = nxt
            else:
                nxt = [o ^ a for o in cur]
                for n in nxt:
                    cur.add(n)

        print('0' if 0 in cur else '1')
main()


Fixed submission:
def collapse(A):
    R = []
    a = max(A)
    n = a.bit_length()
    B = [set() for _ in range(n)]
    for a in A:
        B[a.bit_length()].add(a)
    for i in reversed(range(n)):
        if not B[i]:
            continue
        b = B[i].pop()
        R.append(b)
        for k in B[i]:
            k ^= b
            B[k.bit_length()].add(k)
    return R

def solve(N, A, S):
    B = [0] * 64
    for a, s in zip(reversed(A), reversed(S)):
        if s == '1':
            n = a.bit_length() - 1
            while a != 0:
                if B[n] == 0:
                    return 1
                a ^= B[n]
                n = a.bit_length() - 1
        else:
            n = a.bit_length() - 1
            while a != 0 and B[n] != 0:
                a ^= B[n]
                n = a.bit_length() - 1
            if a == 0:
                continue
            B[n] = a
    return 0
    
def main():
    T = int(input())
    for _ in range(T):
        N = int(input())
        A = list(map(int, input().split()))
        S = input()
        print(solve(N, A, S))
main()
Buggy python submission (verdict: Runtime Error):
from math import gcd

def main():
    N = int(input())
    mod = 10**9 + 7
    AB = {}
    pos = set()
    for _ in range(N):
        a, b = map(int, input().split())
        g = gcd(a, b)
        a, b = a // g, b // g
        if a * b < 0 and a > 0:
            a, b = -a, -b
        if a * b > 0 and a < 0:
            a, b = -a, -b
        if a * b == 0:
            a, b = abs(a), abs(b)
        if a * b > 0:
            pos.add((a, b))
        AB[(a, b)] = AB.get((a, b), 0) + 1
    t = N - AB.get((0, 0), 0)
    r = 1
    for a, b in pos:
        p = AB[(a, b)]
        n = AB.get((-b, a), 0)
        r *= (pow(2, p, mod) - 1) + (pow(2, n, mod) - 1) + 1
        r %= mod
        t -= (p + n)
    p = AB.get((0, 1), 0)
    n = AB.get((1, 0), 0)
    r *= (pow(2, p, mod) - 1) + (pow(2, n, mod) - 1) + 1
    t -= (p + n)
    r *= pow(2, t, mod)
    r -= 1

    if (0, 0) in AB:
        r += AB[(0, 0)]

    return r % mod

print(main())


Fixed submission:
from math import gcd

def main():
    N = int(input())
    mod = 10**9 + 7
    AB = {}
    pos = set()
    for _ in range(N):
        a, b = map(int, input().split())
        g = gcd(a, b)
        if g == 0:
            AB[(0, 0)] = AB.get((0, 0), 0) + 1
            continue
        a, b = a // g, b // g
        if a * b < 0 and a > 0:
            a, b = -a, -b
        if a * b > 0 and a < 0:
            a, b = -a, -b
        if a * b == 0:
            a, b = abs(a), abs(b)
        if a * b > 0:
            pos.add((a, b))
        AB[(a, b)] = AB.get((a, b), 0) + 1
    t = N - AB.get((0, 0), 0)
    r = 1
    for a, b in pos:
        p = AB[(a, b)]
        n = AB.get((-b, a), 0)
        r *= (pow(2, p, mod) - 1) + (pow(2, n, mod) - 1) + 1
        r %= mod
        t -= (p + n)
    p = AB.get((0, 1), 0)
    n = AB.get((1, 0), 0)
    r *= (pow(2, p, mod) - 1) + (pow(2, n, mod) - 1) + 1
    t -= (p + n)
    r *= pow(2, t, mod)
    r -= 1

    if (0, 0) in AB:
        r += AB[(0, 0)]

    return r % mod

print(main())
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, M, K = list(map(int, input().split()))
    mod = 998244353
    r = 0
    m = 1
    for i in range(K + 1):
        if i > 0:
            m = m * (N - i) // i
        r += M * pow(M - 1, N - i - 1, mod) * m

    return r % mod

print(main())


Fixed submission:
def main():
    N, M, K = list(map(int, input().split()))
    mod = 998244353
    r = 0
    m = 1
    inv = [0] * (N + 1)
    inv[1] = 1
    for i in range(2, N + 1):
        inv[i] = inv[mod % i] * ((mod - mod // i) % mod)
    for i in range(K + 1):
        if i > 0:
            m = (m * (N - i) * inv[i]) % mod
        r += M * pow(M - 1, N - i - 1, mod) * m

    return r % mod

print(main())