




from __future__ import annotations




def 		A_	(							snake_case							:				list	, snake_case							:				list	) ->      list:



						'''simple docstring'''

						__UpperCamelCase       					=     [None] * (len(snake_case	) + len(snake_case	))

						__UpperCamelCase       					=     0  # pointer to current index for left Half
						__UpperCamelCase       					=     0  # pointer to current index for the right Half
						__UpperCamelCase       					=     0  # pointer to current index for the sorted array Half

						while pointera < len(snake_case	) and pointera < len(snake_case	):
												if left_half[pointera] < right_half[pointera]:
																		__UpperCamelCase       					=     left_half[pointera]
																		pointera += 1
																		index += 1
												else:
																		__UpperCamelCase       					=     right_half[pointera]
																		pointera += 1
																		index += 1
						while pointera < len(snake_case	):
												__UpperCamelCase       					=     left_half[pointera]
												pointera += 1
												index += 1

						while pointera < len(snake_case	):
												__UpperCamelCase       					=     right_half[pointera]
												pointera += 1
												index += 1

						return sorted_array




def 		A_	(							snake_case							:				list	) ->      list:



						'''simple docstring'''

						if len(snake_case	) <= 1:
												return array
						# the actual formula to calculate the middle element = left + (right - left) // 2
						# this avoids integer overflow in case of large N
						__UpperCamelCase       					=     0 + (len(snake_case	) - 0) // 2

						# Split the array into halves till the array length becomes equal to One
						# merge the arrays of single length returned by mergeSort function and
						# pass them into the merge arrays function which merges the array
						__UpperCamelCase       					=     array[:middle]
						__UpperCamelCase       					=     array[middle:]

						return merge(merge_sort(snake_case	)	, merge_sort(snake_case	)	)


if __name__ == "__main__":
				import doctest

				doctest.testmod()






def 		A_	(							snake_case							:				Union[str, Any]	, snake_case							:				Tuple	, snake_case							:				Optional[Any]	) ->      Union[str, Any]:



						'''simple docstring'''

						assert b != 0, "This cannot accept modulo that is == 0"
						if n == 0:
												return 1

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

						__UpperCamelCase       					=     bin_exp_mod(snake_case	, n / 2	, snake_case	)
						return (r * r) % b


if __name__ == "__main__":
				try:
								lowercase__							:							Dict													=     int(input("Enter Base : ").strip())
								lowercase__							:							Dict													=     int(input("Enter Power : ").strip())
								lowercase__							:							Dict													=     int(input("Enter Modulo : ").strip())
				except ValueError:
								print("Invalid literal for integer")

				print(bin_exp_mod(BASE, POWER, MODULO))




