Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
def solve():
    import sys
    file_input = sys.stdin
    
    def marked_ancestor(v):
        if v == ancestor[v]:
            return v
        else:
            ancestor[v] = marked_ancestor(parent[v])
            return ancestor[v]
    
    def line_ans(line):
        v = int(line[2:])
        if line[0] == 'M':
            ancestor[v] = v
            return 0
        else:
            return marked_ancestor(v)
    
    while True:
        N, Q = map(int, file_input.readline().split())
        if N == 0:
            break
        parent = [None, None]
        parent += [int(file_input.readline()) for _ in range(N - 1)]
        ancestor = [1] * (N + 1)
        ans = (line_ans(file_input.readline()) for _ in range(Q))
        print(sum(ans))

solve()


Fixed submission:
class UnionFind:
    def __init__(self, size):
        self.table = [None] * size

    def find(self, x):
        if self.table[x] == None:
            return x
        else:
            # compression of the path
            self.table[x] = self.find(self.table[x])
            return self.table[x]
    
    def union(self, parent, child):
        p_root = self.find(parent)
        c_root = self.find(child)
        if p_root != c_root:
            self.table[c_root] = p_root
        
def solve():
    import sys
    input_lines = sys.stdin.readlines()
    while True:
        N, Q = map(int, input_lines[0].split())
        if N == 0:
            break
        
        parent = [0, 1] + list(map(int, input_lines[1:N]))
        
        unmarked = [True] * (N + 1)
        unmarked[1] = False
        operation = []
        for o in input_lines[N:N+Q]:
            mq, v = o.split()
            v = int(v)
            if mq == 'M':
                if unmarked[v]:
                    unmarked[v] = False
                    operation.append((mq, v))
            else:
                operation.append((mq, v))
        
        uf = UnionFind(N + 1)
        for v, p in enumerate(parent[2:], start=2):
            if unmarked[v]:
                uf.union(p, v)
        
        ans = 0
        for mq, v in reversed(operation):
            if mq == 'M':
                uf.union(parent[v], v)
            else:
                ans += uf.find(v)
        
        print(ans)
        
        del input_lines[:N+Q]

solve()
Buggy python submission (verdict: Time Limit Exceeded):
def solve():
    n = int(input())
    A = map(int, input().split())
    W = [0] * (n + 1)
    for a_i in A:
        W[a_i] = max(W[:a_i]) + a_i
    ans = n * (n + 1) // 2 - max(W)
    print(ans)

solve()


Fixed submission:
def solve():
    n = int(input())
    dp = [0] * (n + 1)
    
    def update(i, x):
        while i <= n:
            if dp[i] < x:
                dp[i] = x
            i += i & -i
    
    def get_sum(i):
        s = 0
        while i > 0:
            t = dp[i]
            if s < t:
                s = t
            i -= i & -i
        return s
    
    A = map(int, input().split())
    
    for a_i in A:
        update(a_i, get_sum(a_i - 1) + a_i)
    
    ans = n * (n + 1) // 2 - get_sum(n)
    print(ans)

solve()
Buggy python submission (verdict: Runtime Error):
answer_list = [1, 1] + [None] * 43

def fib(num):
    ans = answer_list[num]
    if ans:
        return ans
    ans = fib(num - 1) + fib(num - 2)
    answer_list[num] = ans
    return ans


n = int(input)

print(fib(n))

Fixed submission:
def deco_fibo(func):
    answer_list = [1, 1] + [None] * 43
    def main_fibo(i):
        ans = answer_list[i]
        if ans:
            return ans
        ans = func(i)
        answer_list[i] = ans
        return ans
    return main_fibo

@deco_fibo
def fibo(num):
    return fibo(num - 1) + fibo(num - 2)


n = int(input())

print(fibo(n))
Buggy python submission (verdict: Runtime Error):
n = int(input())

adj = [None]
for i in range(n):
    adj_i = list(map(int, input().split()[2:]))
    adj.append(adj_i)

distance = [None] + [-1] * n

def bfs(u, d):
    pd = distance[u]
    if pd == -1 or d < pd:
        distance[u] = d
    for v in adj[u]:
        bfs(v, d + 1)


bfs(1, 0)

for i, d in enumerate(distance[1:], start=1):
    print(i, d)

Fixed submission:
n = int(input())

adj = [None]
for i in range(n):
    adj_i = list(map(int, input().split()[2:]))
    adj.append(adj_i)

isSearched = [None] + [False] * n

distance = [None] + [-1] * n

import collections

def bfs(u):
    isSearched[u] = True
    distance[u] = 0
    edge = collections.deque()
    edge.append(u)
    while edge:
        c_e = edge.popleft()
        for n_e in adj[c_e]:
            if not isSearched[n_e]:
                isSearched[n_e] = True
                distance[n_e] = distance[c_e] + 1
                edge.append(n_e)


bfs(1)

for i, x in enumerate(distance[1:], start=1):
    print(i, x)
Buggy python submission (verdict: Time Limit Exceeded):
import sys

f_i = sys.stdin

n = int(f_i.readline())

adj = [list(map(int, x.split()[2:])) for x in f_i]

unvisited = [v for v in range(n)]

distance = [999900001] * n
distance[0] = 0

class VCost:
    def __init__(self, v, cost):
        self.v = v
        self.cost = cost
    def __lt__(self, other):
        return self.cost < other.cost

import heapq

vcost = [VCost(0, 0)]

def dijkstra():
    while vcost:
        uc = heapq.heappop(vcost)

        if uc.cost > distance[uc.v]:
            continue
        
        unvisited.remove(uc.v)
        
        for v, c in zip(adj[uc.v][::2], adj[uc.v][1::2]):
            if v in unvisited:
                t_cost = uc.cost + c
                if t_cost < distance[v]:
                    distance[v] = t_cost
                    heapq.heappush(vcost, VCost(v, t_cost))



dijkstra()

for v, d in enumerate(distance):
    print(v, d)

Fixed submission:
import sys

f_i = sys.stdin

n = int(f_i.readline())

adj = [[]] * n
for x in f_i:
    x = list(map(int, x.split()))
    adj[x[0]] = (c_v for c_v in zip(x[3::2], x[2::2]))

import heapq

def dijkstra():
    PQ = [(0, 0)]
    isVisited = [False] * n
    distance = [999900001] * n

    distance[0] = 0
    
    while PQ:
        uc, u = heapq.heappop(PQ)

        if uc > distance[u]:
            continue

        isVisited[u] = True
        
        for vc, v in adj[u]:
            if isVisited[v] == True:
                continue
            
            t_cost = distance[u] + vc
            if t_cost < distance[v]:
                distance[v] = t_cost
                heapq.heappush(PQ, (t_cost, v))

    for v, d in enumerate(distance):
        print(v, d)


dijkstra()
Buggy python submission (verdict: Time Limit Exceeded):
n = input()
n = int(n)

price_list = []

x = input()
x = int(x)

price_list.append(x)

max_profit_candidate = 1 - 10**9

for i in range(n - 1):
    x = input()
    x = int(x)
    diff = x - min(price_list)
    if diff > max_profit_candidate:
        max_profit_candidate = diff
    price_list.append(x)

print(max_profit_candidate)

Fixed submission:
n = input()
n = int(n)

x = input()
x = int(x)

present_min_value = x
max_profit_candidate = 1 - 10**9

for i in range(n - 1):
    a = input()
    a = int(a)
    diff = a - present_min_value
    if diff > max_profit_candidate:
        max_profit_candidate = diff
    if a < present_min_value:
        present_min_value = a

print(max_profit_candidate)
Buggy python submission (verdict: Runtime Error):
import collections
import sys

S1 = collections.deque()
S2 = collections.deque()

f = open('in47', 'r')

for i, j in enumerate(f.readline()):
    if j == '\\':
        S1.append(i)
    elif j == '/':
        if S1:
            left_edge = S1.pop()
            new_puddle = i - left_edge
            while S2 and (S2[-1][0] > left_edge):
                new_puddle += S2[-1][1]
                S2.pop()
            S2.append((left_edge, new_puddle))
        else:
            pass


print(sum(j for i, j in S2))

print(len(S2), *(j for i, j in S2))

Fixed submission:
import collections
import sys

S1 = collections.deque()
S2 = collections.deque()

for i, j in enumerate(sys.stdin.readline()):
    if j == '\\':
        S1.append(i)
    elif j == '/':
        if S1:
            left_edge = S1.pop()
            new_puddle = i - left_edge
            while S2 and (S2[-1][0] > left_edge):
                new_puddle += S2[-1][1]
                S2.pop()
            S2.append((left_edge, new_puddle))
        else:
            pass


print(sum(j for i, j in S2))

print(len(S2), *(j for i, j in S2))
Buggy python submission (verdict: Time Limit Exceeded):
def solve(A, i, m, n):
    """Return if it is possible to make value m with some elements in A.

    n is length of A.
    i is index.
    Using Divide-and-Conquer method.
    """

    if m == 0:
        return True
    if i >= n:
        return False
    return solve(A, i + 1, m, n) or solve(A, i + 1, m - A[i], n)


n = int(input())

A = list(map(int, input().split()))

x = input()

M = list(map(int, input().split()))

for m in M:
    if solve(A, 0, m, n):
        print('yes')
    else:
        print('no')

Fixed submission:
def solve(A, i, m, n):
    """Return if it is possible to make value m with some elements in A.

    n is length of A.
    i is index.
    R is the record of answer i, m.
    Using Divide-and-Conquer method.
    """

    if R[i][m] != None:
        return R[i][m]
    if m == 0:
        R[i][m] = True
        return True
    elif i >= n:
        R[i][m] = False
        return False
    else:
        ans = solve(A, i + 1, m, n) or solve(A, i + 1, m - A[i], n)
        R[i][m] = ans
        return ans


import sys

n = int(sys.stdin.readline())
A = tuple(map(int, sys.stdin.readline().split()))
q = int(sys.stdin.readline())
M = tuple(map(int, sys.stdin.readline().split()))

s_A = sum(A)
R = [[None] * 2000 for i in range(n + 1)]

ans = ''

for m in M:
    if s_A < m:
        ans += 'no\n'
    elif solve(A, 0, m, n):
        ans += 'yes\n'
    else:
        ans += 'no\n'

print(ans, end = '')

Buggy python submission (verdict: Time Limit Exceeded):
def solve(A, i, m, n):
    """Return if it is possible to make value m with some elements in A.

    n is length of A.
    i is index.
    Using Divide-and-Conquer method.
    """

    if m == 0:
        return True
    if i >= n:
        return False
    if m < 0:
        return False
    return solve(A, i + 1, m, n) or solve(A, i + 1, m - A[i], n)


n = int(input())

A = list(map(int, input().split()))

x = input()

M = list(map(int, input().split()))

for m in M:
    if solve(A, 0, m, n):
        print('yes')
    else:
        print('no')

Fixed submission:
def solve(A, i, m, n):
    """Return if it is possible to make value m with some elements in A.

    n is length of A.
    i is index.
    R is the record of answer i, m.
    Using Divide-and-Conquer method.
    """

    if R[i][m] != None:
        return R[i][m]
    if m == 0:
        R[i][m] = True
        return True
    elif i >= n:
        R[i][m] = False
        return False
    else:
        ans = solve(A, i + 1, m, n) or solve(A, i + 1, m - A[i], n)
        R[i][m] = ans
        return ans


import sys

n = int(sys.stdin.readline())
A = tuple(map(int, sys.stdin.readline().split()))
q = int(sys.stdin.readline())
M = tuple(map(int, sys.stdin.readline().split()))

s_A = sum(A)
R = [[None] * 2000 for i in range(n + 1)]

ans = ''

for m in M:
    if s_A < m:
        ans += 'no\n'
    elif solve(A, 0, m, n):
        ans += 'yes\n'
    else:
        ans += 'no\n'

print(ans, end = '')
Buggy python submission (verdict: Time Limit Exceeded):
# Acceptance of input
import sys

file_input = sys.stdin

n = file_input.readline()

EP = []

for line in file_input:
    x1, y1, x2, y2 = (map(int, line.split()))
    # point[2]: 1; left, 2; lower, 3; upper, 4; right
    if y1 < y2:
        p1 = (x1, y1, 2)
        p2 = (x2, y2, 3)
    elif y1 > y2:
        p1 = (x1, y1, 3)
        p2 = (x2, y2, 2)
    elif x1 < x2:
        p1 = (x1, y1, 1)
        p2 = (x2, y2, 4)
    else:
        p1 = (x1, y1, 4)
        p2 = (x2, y2, 1)
    EP += [p1, p2]

# Sweep function
import bisect

def manhattan_intersection(point_list):
    point_list.sort(key = lambda p: (p[1], p[0], p[2]))
    T = []
    cnt = 0
    flag = False
    for p in point_list:
        position = p[2]
        if position == 3:
            T.remove(p[0])
            if flag:
                cnt += 1
        elif position == 2:
            bisect.insort(T, p[0])
        elif position == 4:
            cnt += bisect.bisect(T, p[0]) - left_end
            flag = False
        else:
            left_end = bisect.bisect_left(T, p[0])
            flag = True
    print(cnt)

# Output
manhattan_intersection(EP)

Fixed submission:
# Acceptance of input
import sys

file_input = sys.stdin

n = file_input.readline()

EP = []
l = -1000000001
u = 1000000001
vs_x = set()
h_num = 0

for line in file_input:
    x1, y1, x2, y2 = (map(int, line.split()))
    if x1 == x2:
        if y1 < y2:
            EP.append((y1, l, x1))
            EP.append((y2, u, x1))
        else:
            EP.append((y1, u, x1))
            EP.append((y2, l, x1))
        vs_x.add(x1)
    else:
        if x1 < x2:
            EP.append((y1, x1, x2))
        else:
            EP.append((y1, x2, x1))
        h_num += 1

# Binary Indexed Tree
class BinaryIndexedTree:
    def __init__(self, n):
        self.data = [0] * (n + 1)
        self.num = n

    def switch(self, i, d):
        while  i <= self.num:
            self.data[i] += d
            i += i & -i

    def _sum(self, i):
        s = 0
        while i:
            s += self.data[i]
            i -= i & -i
        return s

    def seg_sum(self, a, b):
        return self._sum(b) - self._sum(a - 1)

# Sweep
import bisect

EP.sort()
BIT = BinaryIndexedTree(len(vs_x))
vs_x = [l] + sorted(vs_x)
d_vs_x = {e: i for i, e in enumerate(vs_x)}
cnt = 0

for p in EP:
    e = p[1]
    if e == l:
        BIT.switch(d_vs_x[p[2]], 1)
    elif e == u:
        BIT.switch(d_vs_x[p[2]], -1)
    else:
        l_x = bisect.bisect_left(vs_x, e)
        r_x = bisect.bisect(vs_x, p[2]) - 1
        cnt += BIT.seg_sum(l_x, r_x)
        h_num -= 1
    if h_num == 0:
        break

# Output
print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
import itertools

def coin_change(coins, val):
    num = 1
    while True:
        for subset in itertools.combinations_with_replacement(coins, num):
            if sum(subset) == val:
                return num
        num += 1

n, m = map(int, input().split())

c = list(map(int, input().split()))

ans = coin_change(c, n)

print(ans)

Fixed submission:
def coin_change(coins, payment):
    T = [0] + [50001] * payment
    for c in coins:
        for i, t in enumerate(zip(T[c:], T), start=c):
            a, b = t
            T[i] = min(a, b + 1)
    return T[payment]

n, m = map(int, input().split())

c = list(map(int, input().split()))

ans = coin_change(c, n)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys

def solve():
    file_input = sys.stdin
    N, W = map(int, file_input.readline().split())
    C = [0] * (W + 1)
    for line in file_input:
        item_v, item_w = map(int, line.split())
        for i, sv in enumerate(C[:-item_w]):
            V = [v + item_v * j for j, v in enumerate(C[i + item_w::item_w], start=1)]
            C[i] = max(V + [sv])
    print(C[0])

solve()

Fixed submission:
import sys

def solve():
    file_input = sys.stdin
    N, W = map(int, file_input.readline().split())
    C = [0] * (W + 1)
    for line in file_input:
        item_v, item_w = map(int, line.split())
        for i, vals in enumerate(zip(C, C[item_w:]), start=item_w):
            v1, v2 = vals
            C[i] = max(v1 + item_v, v2)
    print(C[W])

solve()
Buggy python submission (verdict: Time Limit Exceeded):
import sys

def solve():
    A = list(map(int, sys.stdin.readlines()))
    n = A[0]
    A[0] = -1
    L = [0] * (n + 1)
    for i, a_i in enumerate(A[1:], start=1):
        k = 0
        for j, a_j in enumerate(A[:i]):
            if a_j < a_i and L[j] > L[k]:
                k = j
        L[i] = L[k] + 1
    print(max(L))

solve()

Fixed submission:
import sys
from bisect import bisect_left

def solve():
    A = map(int, sys.stdin)
    n = next(A)
    L = [next(A)]
    for a_i in A:
        if a_i > L[-1]:
            L.append(a_i)
        else:
            j = bisect_left(L, a_i)
            L[j] = a_i
    print(len(L))

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

A = [2147483647] * n

def update(i, x):
    A[i] = x

def find(s, t):
    print(min(A[s:t+1]))


for i in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        update(x, y)
    else:
        find(x, y)

Fixed submission:
import math

n, q = map(int, input().split())

# make a list whose length is 2^i - 1.
n = 2 ** math.ceil(math.log(n, 2))
max_v = 2147483647

A = [max_v for i in range(2 * n - 1)]


def update(i, x):
    i += n - 1
    A[i] = x

    while i > 0:
        i = (i - 1) // 2
        A[i] = min(A[i * 2 + 1], A[i * 2 + 2])

def find(a, b, k, l, r):
    if r <= a or b <= l:
        return max_v
    elif a <= l and r <= b:
        return A[k]
    else:
        vl = find(a, b, k * 2 + 1, l, (l + r) // 2)
        vr = find(a, b, k * 2 + 2, (l + r) // 2, r)
        return min(vl, vr)


for i in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        update(x, y)
    else:
        ans = find(x, y + 1, 0, 0, n)
        print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, q = map(int, input().split())

A = [0 for i in range(n + 1)]

for i in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        A[x] += y
    else:
        s = sum(A[x:y+1])
        print(s)

Fixed submission:
import sys
import math

f_i = sys.stdin

n, q = map(int, f_i.readline().split())

# make a balanced binary tree.
n = 2 ** math.ceil(math.log(n, 2))

A = [0 for i in range(2 * n - 1)]

# operating function
def add(i, x):
    # note; argument i is 1-based.
    i += n - 2
    A[i] += x

    while i > 0:
        i = (i - 1) // 2
        A[i] += x

def getSum(s, t, k, l, r):
    if r < s or t < l:
        return 0
    elif s <= l and r <= t:
        return A[k]
    else:
        mid = (l + r) // 2
        lsum = getSum(s, t, k * 2 + 1, l, mid)
        rsum = getSum(s, t, k * 2 + 2, mid + 1, r)
        return lsum + rsum

for s_i in f_i:
    com, x, y = map(int, s_i.split())
    if com == 0:
        add(x, y)
    else:
        ans = getSum(x, y, 0, 1, n)
        print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# Acceptance of input
import sys

file_input = sys.stdin

V, E = map(int, file_input.readline().split())

adj = [[] for i in range(V)]

for i in range(E):
    s, t = map(int, file_input.readline().split())
    adj[s].append(t)


# dfs path detect
import collections

def isConnected(u, v):
    path = collections.deque()
    path.append(u)

    notVisited = [True] * V
    notVisited[u] = False

    while path:
        e = path[-1]
        for n in adj[e]:
            if n == v:
                return True
            elif notVisited[n]:
                path.append(n)
                notVisited[n] = False
        if e == path[-1]:
            path.pop()

    return False

def isStronglyConnected(u, v):
    if isConnected(u, v) and isConnected(v, u):
        print(1)
    else:
        print(0)


# Output
Q = file_input.readline()

for line in file_input:
    u, v = map(int, line.split())
    isStronglyConnected(u, v)

Fixed submission:
# Acceptance of input
import sys

file_input = sys.stdin

V, E = map(int, file_input.readline().split())

adj = [[] for i in range(V)]

for i in range(E):
    s, t = map(int, file_input.readline().split())
    adj[s].append(t)

# Tarjan's strongly connected components algorithm(repetition)
import collections

S = collections.deque()
path = collections.deque()
index = 0
indices = [None] * V
lowlink = [None] * V
onStack = [False] * V
scc_id = [None] * V
parent = [0] * V

for v in range(V):
    if not indices[v]:
        index += 1
        indices[v] = index
        lowlink[v] = index
        S.append(v)
        path.append(v)
        onStack[v] = True

        while path:
            s = path[-1]
            adj_v = adj[s]
            for t in adj_v:
                if not indices[t]:
                    parent[t] = s
                    path.append(t)
                    S.append(t)
                    index += 1
                    indices[t] = index
                    lowlink[t] = index
                    onStack[t] = True
                    adj_v.remove(t)
                    break
            if s == path[-1]:
                for t in adj_v:
                    if onStack[t]:
                        lowlink[s] = min(lowlink[s], lowlink[t])
                p = parent[s]
                lowlink[p] = min(lowlink[p], lowlink[s])
                if indices[s] == lowlink[s]:
                    while S:
                        w = S.pop()
                        onStack[w] =False
                        scc_id[w] = s
                        if w == s:
                            break
                path.pop()


# Output
Q = file_input.readline()

for line in file_input:
    u, v = map(int, line.split())
    if scc_id[u] == scc_id[v]:
        print(1)
    else:
        print(0)
Buggy python submission (verdict: Runtime Error):
import math

x1, y1, x2, y2 = map(int, input().split())

dx = x1 - x2
dy = y1 - y2

d = math.hypot(dx, dy)

print(d)

Fixed submission:
import math

x1, y1, x2, y2 = map(float, input().split())

dx = x1 - x2
dy = y1 - y2

d = math.hypot(dx, dy)

print(d)
Buggy python submission (verdict: Runtime Error):
import math

r = input()
r = int(r)

area = math.pi * (r ** 2)
length = 2 * math.pi * r

print("{0:.5f} {1:.5f}".format(area, length))

Fixed submission:
import math

r = input()
r = float(r)

area = math.pi * (r ** 2)
length = 2 * math.pi * r

print("{0:.5f} {1:.5f}".format(area, length))
Buggy python submission (verdict: Time Limit Exceeded):
def is_prime(x):
    # Perform prime number discrimination for odd numbers of 3 or more.
    return pow(2, x - 1, x) == 1

def solve():
    n = int(input())
    ans = []
    print("{}: ".format(n), end='')
    
    while n % 2 == 0:
        n //= 2
        ans.append(2)

    d = 3
    while n >= d:
        if is_prime(d):
            while n % d == 0:
                n //= d
                ans.append(d)
        d += 2

    print(*ans)

solve()

Fixed submission:
def is_prime(x):
    # Perform prime number discrimination for odd numbers of 3 or more.
    return pow(2, x - 1, x) == 1

def solve():
    n = int(input())
    print("{}: ".format(n), end='')
    if is_prime(n):
        print(n)
    else:
        ans = []
        while n % 2 == 0:
            n //= 2
            ans.append(2)
        d = 3
        while d <= n ** 0.5:
            if is_prime(d):
                while n % d == 0:
                    n //= d
                    ans.append(d)
            d += 2
        if is_prime(n):
            ans.append(n)
        print(*ans)

solve()
Buggy python submission (verdict: Time Limit Exceeded):
def solve():
    m, n = map(int, input().split())
    print(m ** n % 1000000007)

solve()

Fixed submission:
d = 1000000007

def pow_rem(x, n):
    if n == 0:
        return x ** n % d
    if n % 2 == 0:
        return pow_rem(x, n // 2) ** 2 % d
    else:
        return ((pow_rem(x , n // 2) ** 2) * x) % d

def solve():
    m, n = map(int, input().split())
    print(pow_rem(m, n))

solve()

Buggy python submission (verdict: Runtime Error):
d = 1000000007

def pow_rem(x, n):
    if n == 0:
        return x ** n % d
    if n % 2 == 0:
        return pow_rem(x, n // 2) ** 2 % d
    else:
        return ((pow_rem(x , n // 2) ** 2) * x) % d

def solve():
    m, n = map(int, input().split())
    print(pow_rem(m, n)

solve()

Fixed submission:
d = 1000000007

def pow_rem(x, n):
    if n == 0:
        return x ** n % d
    if n % 2 == 0:
        return pow_rem(x, n // 2) ** 2 % d
    else:
        return ((pow_rem(x , n // 2) ** 2) * x) % d

def solve():
    m, n = map(int, input().split())
    print(pow_rem(m, n))

solve()