chacha-chaudhary-and-sabu

Babu and Sabu are enemies but they fight with each other with the help of the mind games not guns. One day Babu asks Sabu to give the answer for this mathematical query as following:

Let f(m, n) = m^n

But Sabu is little weak in mathematics and he wants the help to answer the question.

Your aim is to answer f(m1, n1)^f(m2,n2) % n

Can you help Sabu to give answer of question to Babu.

INPUT:

You are given T which is the number of queries to solve.

Each Query consist of 5 space separated integers m1, n1, m2, n2, n.

OUTPUT:

Output contains exactly T lines. i th line containing the answer for the i th query.

Constraints:

1 ≤ T ≤ 10000 

0 ≤ m1, n1, m2, n2, n ≤ 1000000000

1 ≤ n ≤ 10000000

SAMPLE INPUT
1
2 1 2 2 15

SAMPLE OUTPUT
1

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
#http://ideone.com/bOxFqJ
#http://stackoverflow.com/questions/4223313/finding-abc-mod-m
def totient(n) :          
	result = 1
	p = 2                 
	while p**2 <= n :
		if(n%p == 0) :    
			result *= (p-1)
			n /= p
		while(n%p == 0) :
			result *=  p
			n /= p
		if p==2:
			p += 1
		else:
			p += 2
	if n != 1 :
		result *= (n-1)
	return result
 
def modpow(p, z, b, c, m) : 
	if m == 2:
		return p % m
	cp = 0
	while m % p == 0 :
		cp += 1
		m /= p              
	t = totient(m)
	exponent = ((pow(b,c,t)*z)%t + t - (cp%t))%t                            
	return pow(p, cp)*pow(p, exponent, m)
from fractions import gcd 
def solve(a,b,c,m) : #split
	result = 1
	p = 2
	while p**2 <= a :
		cp = 0
		while a%p == 0 :
			a /= p
			cp += 1
		if cp != 0 :
		   temp =  modpow(p,cp,b,c,m)
		   result *= temp
		   result %= m
		p += 1
	if a != 1 :
		result *= modpow(a, 1, b, c, m)
	return result % m
T = eval(input())
#print pow(0,0,1)
import sys
for i in range(T):
	m1,n1,m2,n2,n = list(map(int,sys.stdin.readline().split()))
	x = pow(m1,n1,n)
	if n==1:
		print(0) 
		continue
	if x==1:
		print(1)
		continue
	
	
	else:
		
		if m2 < 10**2 and n2 < 10**1:
			y = pow(m2,n2)
			print(pow(x,y,n))
			continue
		if x ==0:
			print(0)
			continue
		print(solve(x,m2,n2,n))