



'''simple docstring'''







from __future__ import annotations

from collections import defaultdict
from dataclasses import dataclass




@dataclass
class 				__lowerCAmelCase:
			__snake_case  :		int
			__snake_case  :		TreeNode | None		=      None
			__snake_case  :		TreeNode | None		=      None







def  SCREAMING_SNAKE_CASE__ (				):
		return TreeNode(3 ,		TreeNode(9     ) ,		TreeNode(20 ,		TreeNode(15     ) ,		TreeNode(7     )     )     )







def  SCREAMING_SNAKE_CASE__ (				SCREAMING_SNAKE_CASE     ):

		def depth_first_search(
		    SCREAMING_SNAKE_CASE ,		SCREAMING_SNAKE_CASE ,		SCREAMING_SNAKE_CASE     ) -> None:
				if not root:
						return

				if depth == len(SCREAMING_SNAKE_CASE     ):
						right_view.append(root.val     )

				depth_first_search(root.right ,		depth + 1 ,		SCREAMING_SNAKE_CASE     )
				depth_first_search(root.left ,		depth + 1 ,		SCREAMING_SNAKE_CASE     )

		SCREAMING_SNAKE_CASE_						:list										=      []
		if not root:
				return right_view

		depth_first_search(SCREAMING_SNAKE_CASE ,		0 ,		SCREAMING_SNAKE_CASE     )
		return right_view







def  SCREAMING_SNAKE_CASE__ (				SCREAMING_SNAKE_CASE     ):

		def depth_first_search(
		    SCREAMING_SNAKE_CASE ,		SCREAMING_SNAKE_CASE ,		SCREAMING_SNAKE_CASE     ) -> None:
				if not root:
						return

				if depth == len(SCREAMING_SNAKE_CASE     ):
						left_view.append(root.val     )

				depth_first_search(root.left ,		depth + 1 ,		SCREAMING_SNAKE_CASE     )
				depth_first_search(root.right ,		depth + 1 ,		SCREAMING_SNAKE_CASE     )

		SCREAMING_SNAKE_CASE_						:list										=      []
		if not root:
				return left_view

		depth_first_search(SCREAMING_SNAKE_CASE ,		0 ,		SCREAMING_SNAKE_CASE     )
		return left_view







def  SCREAMING_SNAKE_CASE__ (				SCREAMING_SNAKE_CASE     ):

		def breadth_first_search(SCREAMING_SNAKE_CASE ,		SCREAMING_SNAKE_CASE     ) -> None:
				SCREAMING_SNAKE_CASE_						:List[str]										=      [(root, 0)]
				SCREAMING_SNAKE_CASE_						:Optional[int]										=      defaultdict(SCREAMING_SNAKE_CASE     )

				while queue:
						SCREAMING_SNAKE_CASE_						:int										=      queue.pop(0     )
						SCREAMING_SNAKE_CASE_						,		SCREAMING_SNAKE_CASE_						:Tuple										=      first

						lookup[hd].append(node.val     )

						if node.left:
								queue.append((node.left, hd - 1)     )
						if node.right:
								queue.append((node.right, hd + 1)     )

				for pair in sorted(lookup.items() ,		key=lambda SCREAMING_SNAKE_CASE     : each[0]     ):
						top_view.append(pair[1][0]     )

		SCREAMING_SNAKE_CASE_						:list										=      []
		if not root:
				return top_view

		breadth_first_search(SCREAMING_SNAKE_CASE ,		SCREAMING_SNAKE_CASE     )
		return top_view







def  SCREAMING_SNAKE_CASE__ (				SCREAMING_SNAKE_CASE     ):
		from collections import defaultdict

		def breadth_first_search(SCREAMING_SNAKE_CASE ,		SCREAMING_SNAKE_CASE     ) -> None:
				SCREAMING_SNAKE_CASE_						:int										=      [(root, 0)]
				SCREAMING_SNAKE_CASE_						:Tuple										=      defaultdict(SCREAMING_SNAKE_CASE     )

				while queue:
						SCREAMING_SNAKE_CASE_						:Optional[Any]										=      queue.pop(0     )
						SCREAMING_SNAKE_CASE_						,		SCREAMING_SNAKE_CASE_						:Optional[int]										=      first
						lookup[hd].append(node.val     )

						if node.left:
								queue.append((node.left, hd - 1)     )
						if node.right:
								queue.append((node.right, hd + 1)     )

				for pair in sorted(lookup.items() ,		key=lambda SCREAMING_SNAKE_CASE     : each[0]     ):
						bottom_view.append(pair[1][-1]     )

		SCREAMING_SNAKE_CASE_						:list										=      []
		if not root:
				return bottom_view

		breadth_first_search(SCREAMING_SNAKE_CASE ,		SCREAMING_SNAKE_CASE     )
		return bottom_view


if __name__ == "__main__":
							import doctest

							doctest.testmod()





'''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))
