You will be given two integers $a,b$. You are required to output the result of $2^{(2^a)}$ mod $\boldsymbol{b}$.

Constraints

$1\leq a,b\leq10^6$

Input Format

First and only line of the input will contain two integers $a,b$ separated by a single blank space.

Output Format

Output the desired result in a single line.

Sample Input
2 7

Sample Output
2

Explanation

$2^a=4$, $2^{4}=16$, and $\mbox{16}$ mod $7$ is $2$.

Difficulty: HARD
Tags: Number theory

Starter code:

Solutions:
ip = input().split(' ')
a = int(ip[0])
b = int(ip[1])
print(pow(2, 2 ** a, b))


(A, B) = (int(_) for _ in input().split())
print(pow(2, 2 ** A, B))


def main():
	(a, b) = map(int, input().split())
	print(pow(2, pow(2, a), b))
main()


(n, m) = map(int, input().split())
x = pow(2, n)
print(pow(2, x, m))


(a, b) = map(int, input().split())
print(pow(2, 2 ** a, b))


a = [int(i) for i in input().split()]
print(pow(2, pow(2, a[0]), a[1]))


(a, b) = [int(x) for x in input().split()]
print(pow(2, 2 ** a, b))


(a, b) = [int(x) for x in input().split()]
print(pow(2, pow(2, a), b))


values = [int(num) for num in input().split()]
a = values[0]
b = values[1]
print(pow(2, pow(2, a), b))


(a, b) = map(int, input().split())

def modexp(g, u, p):
	s = 1
	while u != 0:
		if u & 1:
			s = s * g % p
		u >>= 1
		g = g * g % p
	return s
v = 2
for i in range(a):
	v = v * v % b
print(v)


from math import floor, sqrt, ceil

def factorization(n):
	sqroot = floor(sqrt(n)) + 1
	f = {2: 0}
	while n % 2 == 0:
		f[2] += 1
		n //= 2
	divisor = 3
	while divisor < sqroot and n != 1:
		while n % divisor == 0:
			if divisor in f:
				f[divisor] += 1
			else:
				f[divisor] = 1
			n //= divisor
		divisor += 2
	if n != 1:
		f[n] = 1
	return f

def euler(n):
	f = factorization(n)
	e = 1
	for m in f.keys():
		e *= (m - 1) * pow(m, f[m] - 1)
(a, b) = [int(i) for i in input().split()]
r1 = pow(2, a, euler(b))
r2 = pow(2, r1, b)
print(r2)


(a, b) = map(int, input().split(' '))
lookup = [4 % b]
for i in range(1, a):
	prev = lookup[i - 1]
	lookup.append(prev ** 2 % b)
print(lookup[-1])


import sys
(a, b) = list(map(int, sys.stdin.readline().split()))
x = 2
for _ in range(a):
	x = pow(x, 2, b)
print(x)


(a, b) = list(map(int, input().split()))
res = 2
for _ in range(a):
	res = res ** 2
	res %= b
print(res)


(a, b) = map(int, input().split())
ans = 2
for _ in range(a):
	ans = pow(ans, 2, b)
print(ans)


(a, b) = (int(i) for i in input().split())
answer = 2
for i in range(a):
	answer = answer * answer % b
print(answer)


import sys
(a, b) = list(map(int, sys.stdin.readline().split()))
x = 2
x = pow(x, pow(x, a), b)
print(x)


(a, b) = map(int, input().strip().split())
print(pow(2, 2 ** a, b))


def main():
	s = input()
	(a, b) = s.strip().split(' ')
	a = int(a)
	b = int(b)
	ans = 2
	for i in range(0, a):
		ans = ans * ans
		if ans >= b:
			ans %= b
	print(ans)
main()


(a, b) = map(int, input().split())
print(pow(2, pow(2, a), b))


(a, b) = map(int, input().split())

def calc(a, b):
	if a == 0:
		return 2 % b
	result = 2
	for i in range(a):
		result = result * result % b
	return result
print(calc(a, b))


(lga, b) = map(int, input().strip().split())
acc = 1
curpow = 2
while lga >= 0:
	if lga == 0:
		acc = acc * curpow % b
	curpow = curpow ** 2 % b
	lga -= 1
print(acc)


(a, b) = list(map(int, input().split()))
print(pow(2, pow(2, a), b))


(a, b) = map(int, input().split())
print(pow(2, 2 ** a, b))


(a, b) = [int(x) for x in input().split(' ')]
x = 2
for _ in range(a):
	x = x * x % b
print(x)


def run(a, b):
	if b == 1 or b == 2 or b == 4:
		return 0
	if b == 3:
		return 1
	if a == 1:
		return 4 % b
	last = 4 % b
	res = [last]
	occured = {last: 0}
	for i in range(a):
		last *= last
		last %= b
		if last in occured:
			start_i = occured[last]
			end_i = i
			index = (a - 1 - start_i) % (end_i - start_i + 1) + start_i
			return res[index]
		else:
			res.append(last)
			occured[last] = i + 1
	return last
(a, b) = map(int, input().strip().split())
print(run(a, b))


(a, b) = map(int, input().strip().split())
print(pow(2, pow(2, a), b))


import sys
import math
l = input().strip().split()
a = int(l[0])
b = int(l[1])
n = 2
for i in range(a):
	n = n % b
	n = n * n
	n = n % b
print(n)


ip = input().split(' ')
a = int(ip[0])
b = int(ip[1])
print(pow(2, 2 ** a, b))


import math
(a, b) = map(int, input().split())
print(pow(2, pow(2, a), b))


import sys
(a, b) = list(map(int, sys.stdin.readline().split()))
x = 2
for _ in range(a):
	x = pow(x, 2, b)
print(x)


(a, b) = map(int, input().strip().split(' '))
print(pow(2, 2 ** a, b))


(a, b) = map(int, input().strip().split(' '))
print(pow(2, 2 ** a, b))


(a, b) = [int(x) for x in input().split()]
print(pow(2, pow(2, a), b))


(a, b) = list(map(int, input().split()))
x = 2
for _ in range(a):
	x = pow(x, 2, b)
print(x)


[a, b] = [int(x) for x in input().strip().split(' ')]
cu = 2
for x in range(a):
	cu = cu * cu % b
print(cu)


def primefactor(n):
	if n % 2 == 0:
		yield 2
		while n % 2 == 0:
			n //= 2
	p = 3
	while p * p <= n:
		if n % p == 0:
			yield p
			while n % p == 0:
				n //= p
		p += 2
	if n > 1:
		yield n

def totient(n):
	for p in primefactor(n):
		n = n * (p - 1) // p
	return n
(a, b) = map(int, input().split())
pow2 = 0
while b % 2 == 0:
	(b, pow2) = (b // 2, pow2 + 1)
print(pow(2, (pow(2, a, totient(b)) - pow2) % totient(b), b) * 2 ** pow2)


import math
(a, b) = map(int, input().split(' '))
print(pow(2, pow(2, a), b))


import sys
nums = list(map(lambda x: x.strip(), sys.stdin.readlines()))
nums = nums[0].split()
a = int(nums[0])
b = int(nums[1])
base = 2
for i in range(a):
	base = pow(base, 2)
	base = base % b
print(base)


l = list(map(int, input().split()))
a = l[0]
b = l[1]
print(pow(2, 1 << a, b))


(a, p) = [int(x) for x in input().split()]
ans = 2
while a:
	ans = ans * ans % p
	a -= 1
print(ans)


(a, b) = [int(a) for a in input().split()]
print(pow(2, 2 ** a, b))


from math import log2

def rwh_primes1(n):
	sieve = [True] * (n // 2)
	for i in range(3, int(n ** 0.5) + 1, 2):
		if sieve[i // 2]:
			sieve[i * i // 2::i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
	return [2] + [2 * i + 1 for i in range(1, n // 2) if sieve[i]]
primes = rwh_primes1(10 ** 6 + 1)

def factorization(n):
	factors = {}
	i = 0
	while primes[i] <= n:
		alpha = 0
		while n % primes[i] == 0:
			alpha += 1
			n //= primes[i]
		if alpha:
			factors[primes[i]] = alpha
		i += 1
	return factors
(a, b) = map(int, input().strip().split(' '))
fact_n = factorization(b)
if 2 in fact_n:
	phi = 1
	n1 = pow(2, fact_n[2])
	n2 = b // n1
	for (p, v) in fact_n.items():
		if p == 2:
			continue
		phi *= (p - 1) * pow(p, v - 1)
	e = pow(2, a, phi)
	x2 = pow(2, e, n2)
	if a >= log2(fact_n[2]):
		x1 = 0
	else:
		x1 = pow(2, pow(2, a))
	v1 = pow(n2, n1 // 2 - 1, n1)
	v2 = pow(n1, phi - 1, n2)
	print((x1 * v1 * n2 + x2 * v2 * n1) % b)
else:
	phi = 1
	for (p, v) in fact_n.items():
		phi *= (p - 1) * pow(p, v - 1)
	expo = pow(2, a, phi)
	print(pow(2, expo, b))


(a, b) = map(int, input().split())
print(pow(2, pow(2, a), b))


(a, b) = [int(x) for x in input().split()]
print(pow(2, pow(2, a), b))


(a, b) = [int(x) for x in input().strip().split(' ')]
x = 2
for _ in range(a):
	x = x * x % b
print(x)


import math
(a, b) = map(int, input().split(' '))
base = 2
for i in range(a):
	base = base ** 2 % b
print(int(base))


(a, b) = map(int, input().split())
print(pow(2, pow(2, a), b))


(a, b) = map(int, input().split())
base = 2
for i in range(a):
	base = base ** 2 % b
print(base)


(a, m) = map(int, input().split())
print(pow(2, pow(2, a), m))


(a, b) = map(int, input().split())
n = b
i = 2
f = {}
while n >= i * i:
	while n % i == 0:
		n //= i
		f[i] = f.get(i, 0) + 1
	i += 1
if n > 1:
	f[n] = 1
phi = 1
for (p, e) in f.items():
	phi *= (p - 1) * p ** (e - 1)
x = pow(2, pow(2, a, phi) or phi, b)
print(x)


(a, b) = map(int, input().split())
print(pow(2, pow(2, a), b))


(a, b) = map(int, input().split())
print(pow(2, pow(2, a), b))


(a, b) = map(int, input().split())
n = pow(2, a)
print(pow(2, n, b))


(a, b) = map(int, input().split())
print(pow(2, pow(2, a), b))


(a, b) = map(int, input().split())
print(pow(2, pow(2, a), b))


import sys
(a, b) = list(map(int, sys.stdin.readline().split()))
x = 2
for _ in range(a):
	x = pow(x, 2, b)
print(x)


(a, b) = [int(x) for x in input().split()]
print(pow(2, pow(2, a), b))


(a, b) = map(int, input().split())
print(pow(2, 2 ** a, b))


def bitize(x):
	L = []
	while x > 0:
		L.append(x % 2)
		x //= 2
	if not L:
		L = [0]
	return L

def pow_mod(a, b, m):
	b_bits = bitize(b)
	a_powers = [0 for x in b_bits]
	a_powers[0] = a % m
	if b_bits[0]:
		total = a % m
	else:
		total = 1
	for i in range(1, len(b_bits)):
		a_powers[i] = a_powers[i - 1] * a_powers[i - 1] % m
		if b_bits[i]:
			total *= a_powers[i]
			total %= m
	return total

def is_prime(x, L=[]):
	sqrt = int(pow(x, 0.5)) + 1
	PL = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 16, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199]
	if not L:
		if x < 210:
			if x in PL:
				return True
			else:
				return False
		else:
			for p in PL:
				if x % p == 0:
					return False
			for i in range(1, sqrt // 210 + 1):
				for j in [1, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 121, 127, 131, 137, 139, 143, 149, 151, 157, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199, 209]:
					if x % (210 * i + j) == 0:
						return False
		return True
	elif x != 0 and x != 1:
		j = 0
		while j < len(L) and L[j] <= sqrt:
			if x % L[j] == 0:
				return False
			j += 1
	else:
		return False
	return True

def prime_list(n):
	L = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199]
	for k in range(1, n // 210):
		for j in [1, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 121, 127, 131, 137, 139, 143, 149, 151, 157, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199, 209]:
			if is_prime(210 * k + j, L):
				L.append(210 * k + j)
	k = n // 210
	for j in [1, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 121, 127, 131, 137, 139, 143, 149, 151, 157, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199, 209]:
		if is_prime(210 * k + j, L) and 210 * k + j <= n:
			L.append(210 * k + j)
	return L

def is_miller_rabin(x, num_tests=3):
	k = x - 1
	e = 0
	while k % 2 == 0:
		e += 1
		k //= 2
	tests = [False for _ in range(0, num_tests)]
	A = [2, 3, 5]
	for j in range(3, num_tests):
		A.append(random.randint(7, x - 1))
	if x < 2047:
		num_tests = 1
	elif x < 1373653:
		num_tests = 2
	elif x < 25326001:
		num_tests = 3
	for i in range(0, num_tests):
		ak = pow_mod(A[i], k, x)
		if ak == 1:
			tests[i] = True
		else:
			for j in range(0, e):
				if ak == x - 1:
					tests[i] = True
				ak = ak * ak % x
	for i in range(0, num_tests):
		if not tests[i]:
			return False
	return True

def factor(n, PL):
	sqrt = int(pow(n, 0.5)) + 1
	factor_list = []
	if not PL:
		PL = prime_list(sqrt)
	for p in PL:
		if n % p == 0:
			elet = [p, 0]
			while not n % p:
				n //= p
				elet[1] += 1
			factor_list.append(elet)
	if n != 1:
		if is_miller_rabin(n):
			factor_list.append([n, 1])
	return factor_list

def is_prime(x, L=[]):
	sqrt = int(pow(x, 0.5)) + 1
	PL = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 16, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199]
	if not L:
		if x < 210:
			if x in PL:
				return True
			else:
				return False
		else:
			for p in PL:
				if x % p == 0:
					return False
			for i in range(1, sqrt // 210 + 1):
				for j in [1, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 121, 127, 131, 137, 139, 143, 149, 151, 157, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199, 209]:
					if x % (210 * i + j) == 0:
						return False
		return True
	elif x != 0 and x != 1:
		j = 0
		while j < len(L) and L[j] <= sqrt:
			if x % L[j] == 0:
				return False
			j += 1
	else:
		return False
	return True

def prime_list(n):
	L = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199]
	for k in range(1, n // 210):
		for j in [1, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 121, 127, 131, 137, 139, 143, 149, 151, 157, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199, 209]:
			if is_prime(210 * k + j, L):
				L.append(210 * k + j)
	k = n // 210
	for j in [1, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 121, 127, 131, 137, 139, 143, 149, 151, 157, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199, 209]:
		if is_prime(210 * k + j, L) and 210 * k + j <= n:
			L.append(210 * k + j)
	return L

def euler_totient_with_factors(n, factors):
	for ar_elet in factors:
		n //= ar_elet[0]
		n *= ar_elet[0] - 1
	return n
(a, b) = [int(a) for a in input().split()]
PL = prime_list(50000)
b_factors = factor(b, PL)
phi_b = euler_totient_with_factors(b, b_factors)
print(pow_mod(2, pow_mod(2, a, phi_b) + phi_b, b))


import sys

def primes_gen(n):
	sieve = [True] * n
	for p in range(2, n):
		if sieve[p]:
			yield p
			for i in range(p + p, n, p):
				sieve[i] = False

def pfs_gen(n, prms):
	for p in prms:
		if p > n:
			break
		cnt = 0
		while n % p == 0:
			cnt += 1
			n //= p
		if cnt:
			yield (p, cnt)
	if n > 1:
		yield (n, 1)

def totient(n, prms):
	t = 1
	for (p, c) in pfs_gen(n, prms):
		t *= pow(p, c) - pow(p, c - 1)
	return t

def calc(a, b):
	prms = tuple(primes_gen(b // 2 + 1))
	print('primes generated: %d' % len(prms), file=sys.stderr)
	t = totient(c, prms)
	print('t=%d' % t, file=sys.stderr)
	u = pow(2, t, b)
	print('u=%d' % u, file=sys.stderr)
	pwr = pow(2, a, t)
	v = pow(2, pwr, b)
	return v

def solve(a, b):
	print('a=%d b=%d' % (a, b), file=sys.stderr)
	(c, r) = (b, 0)
	while c % 2 == 0:
		r += 1
		c //= 2
	print('c=%d r=%d' % (c, r), file=sys.stderr)
	prms = tuple(primes_gen(b // 2 + 1))
	print('primes generated: %d' % len(prms), file=sys.stderr)
	t = totient(b, prms)
	print('t=%d' % t, file=sys.stderr)
	u = pow(2, t, b)
	print('u=%d' % u, file=sys.stderr)
	pwr = pow(2, a, t)
	print('pwr=%d' % pwr, file=sys.stderr)
	v = pow(2, pwr, b)
	return u * v % b
(a, b) = map(int, input().split())
print(solve(a, b))


tmp1 = input().strip()
(a, b) = (int(tmp1.split()[0]), int(tmp1.split()[1]))
print(pow(2, pow(2, a), b))


(a, b) = list(map(int, input().split()))
x = 2 ** a
print(pow(2, x, b))


import fractions

def phi(n):
	amount = 0
	for k in range(1, n + 1):
		if fractions.gcd(n, k) == 1:
			amount += 1
	return amount

def pow(x, n, m):
	if n < 30:
		return x ** n % m
	tmp = pow(x, n // 2, m) ** 2 % m
	if n % 2 == 1:
		tmp = tmp * x % m
	return tmp
(a, b) = map(int, input().split())
ans = 2
for _ in range(a):
	ans = ans ** 2 % b
print(ans)


(a, b) = map(int, input().split())
print(pow(2, pow(2, a), b))


(a, b) = map(int, input().split())
print(pow(2, pow(2, a), b))


import math
(a, b) = map(int, input().split(' '))
base = 2
for i in range(a):
	base = base ** 2 % b
print(int(base))


i = input()
(a, b) = [int(x) for x in i.split()]
print(pow(2, pow(2, a), b))


(a, b) = [int(x) for x in input().split(' ')]
print(pow(2, 2 ** a, b))


import math
(a, b) = map(int, input().split(' '))
base = 2
for i in range(a):
	base = base ** 2 % b
print(int(base))


(a, b) = map(int, input().split())
print(pow(2, pow(2, a), b))


import math
(a, b) = map(int, input().split(' '))
base = 2
for i in range(a):
	base = base ** 2 % b
print(int(base))


s = input().split()
(a, b) = (int(s[0]), int(s[1]))
print(pow(2, pow(2, a), b))


(a, b) = map(int, input().split())
print(pow(2, pow(2, a), b))


import math
(a, b) = map(int, input().strip().split(' '))
print(pow(2, pow(2, a), b))


(a, b) = map(int, input().split())
print(pow(2, pow(2, a), b))


(a, b) = map(int, input().split())
print(pow(2, pow(2, a), b))


(a, b) = map(int, input().split())
print(pow(2, pow(2, a), b))


def moduloExp(a, b):
	ret = 2
	for i in range(a):
		ret = ret * ret % b
	return ret
(a, b) = list(map(int, input().rstrip().split()))
print(moduloExp(a, b))


(a, b) = list(map(lambda x: int(x), input().split()))
print(pow(2, pow(2, a), b))


import os
import sys
(a, b) = map(int, input().split())
print(pow(2, pow(2, a), b))


ip = input().split(' ')
a = int(ip[0])
b = int(ip[1])
print(pow(2, 2 ** a, b))


import math
(a, b) = map(int, input().split(' '))
base = 2
for i in range(a):
	base = base ** 2 % b
print(int(base))


(a, b) = map(int, input().split(' '))
print(pow(2, pow(2, a), b))


import math
(a, b) = map(int, input().split(' '))
base = 2
for i in range(a):
	base = base ** 2 % b
print(int(base))


(a, b) = map(int, input().split())
print(pow(2, pow(2, a), b))


(a, b) = map(int, input().split())
print(pow(2, pow(2, a), b))


import math
(a, b) = map(int, input().split(' '))
base = 2
for i in range(a):
	base = base ** 2 % b
print(int(base))


(a, b) = map(int, input().split())
print(pow(2, pow(2, a), b))


(a, b) = map(int, input().split())
print(pow(2, pow(2, a), b))


(a, b) = map(int, input().split())
print(pow(2, pow(2, a), b))


import math
(a, b) = map(int, input().split(' '))
base = 2
for i in range(a):
	base = base ** 2 % b
print(int(base))