def main():
i = int(input())
for _ in range(i):
A, N = map(int, input().split(" "))
ans = solver(N, A)
print(ans)
def solver(N, A):
middle_term = (N+1)//2
series_list = []
for i in range(0, (N + 1)):
x = A ** i
series_list.append(x)
series_list = sorted(series_list)
return series_list[middle_term]
if '__main__' == __name__:
main()

@Deepa_Panwar1, I am sorry for the incomplete post, I intended to ask a question, with reference to the above code snippet. Mentioning it below for reference:

I tried to use this for Integer on Stones, it seems to be working but shows the time limit exceeded error. I am not sure if it completely accurate though it passed the initial test case.

You are calculating all A^i, but is there a way to skip calculating all? Let us see.

If A is positive we know that A^N will always be greater than A^(N-1) which will in turn be greater than A^(N-2) and so on, we can determine that A^(middle_term) will always be the answer.

If A is negative, then the sign of the terms would alternate. So for each positive number, there will also be a matching negative number. So the middle term would be A^0 = 1. E.g. if A = -2, N = 4 then the terms are [1,-2,4,-8,16] and sorting them we will have [-8,-2,1,4,16] so the answer here will be 1

However just this observation alone is not enough. For the first case, you will need to calculate A^(middle_term). But middle_term can be very large. Note that the answer has to be modulo mod. For that there is a technique called modular exponentiation. You can read more about fast modular exponentiation in this and next few lessons on this link.

Here is a sample solution in python for the same:

mod = int(1e9) + 7
def modpow(a, b):
if a == 0:
return 0
global mod
res = 1
while b > 0:
if b % 2 == 1:
res = res * a % mod
a = a * a % mod
b = b // 2
return res
T = int(input())
for _ in range(T):
A, N = map(int, input().split(' '))
ans = 0
if A > 0:
ans = modpow(A, N // 2)
if A < 0:
ans = 1
print(ans)