





'''simple docstring'''







from __future__ import annotations





def 							lowerCamelCase_   (	SCREAMING_SNAKE_CASE__   :      int )			->						list[int]:
						UpperCAmelCase_      :   int      =	[0] * max_one

						for i in range(0,      SCREAMING_SNAKE_CASE__ ):
												UpperCAmelCase_      :   Any      =	i

						for i in range(2,      SCREAMING_SNAKE_CASE__ ):
												if totients[i] == i:
																		for j in range(SCREAMING_SNAKE_CASE__,      SCREAMING_SNAKE_CASE__,      SCREAMING_SNAKE_CASE__ ):
																								totients[j] -= totients[j] // i

						return totients





def 							lowerCamelCase_   (	SCREAMING_SNAKE_CASE__   :      int,      SCREAMING_SNAKE_CASE__   :      int )			->						bool:
						return sorted(str(SCREAMING_SNAKE_CASE__ ) ) == sorted(str(SCREAMING_SNAKE_CASE__ ) )





def 							lowerCamelCase_   (	SCREAMING_SNAKE_CASE__   :      int = 10000000 )			->						int:
						UpperCAmelCase_      :   Optional[Any]      =	1  # i
						UpperCAmelCase_      :   Optional[int]      =	0  # φ(i)
						UpperCAmelCase_      :   List[Any]      =	get_totients(max_n + 1 )

						for i in range(2,      max_n + 1 ):
												UpperCAmelCase_      :   List[Any]      =	totients[i]

												if i * min_denominator < min_numerator * t and has_same_digits(SCREAMING_SNAKE_CASE__,      SCREAMING_SNAKE_CASE__ ):
																		UpperCAmelCase_      :   Union[str, Any]      =	i
																		UpperCAmelCase_      :   Optional[int]      =	t

						return min_numerator


if __name__ == "__main__":
					print(f'''{solution() = }''')










'''simple docstring'''







def  SCREAMING_SNAKE_CASE__ (				SCREAMING_SNAKE_CASE ,		SCREAMING_SNAKE_CASE ,		SCREAMING_SNAKE_CASE     ):
		assert b != 0, "This cannot accept modulo that is == 0"
		if n == 0:
				return 1

		if n % 2 == 1:
				return (bin_exp_mod(SCREAMING_SNAKE_CASE ,		n - 1 ,		SCREAMING_SNAKE_CASE     ) * a) % b

		SCREAMING_SNAKE_CASE_						:List[str]										=      bin_exp_mod(SCREAMING_SNAKE_CASE ,		n / 2 ,		SCREAMING_SNAKE_CASE     )
		return (r * r) % b


if __name__ == "__main__":
							try:
														SCREAMING_SNAKE_CASE__     : Any				=   int(input("""Enter Base : """).strip())
														SCREAMING_SNAKE_CASE__     : str				=   int(input("""Enter Power : """).strip())
														SCREAMING_SNAKE_CASE__     : List[Any]				=   int(input("""Enter Modulo : """).strip())
							except ValueError:
														print("""Invalid literal for integer""")

							print(bin_exp_mod(BASE, POWER, MODULO))
