




from __future__ import annotations

from collections.abc import Iterator
from typing import Any



class      a__				:


			def __init__(      self      :    List[str]      ,  UpperCamelCase_      :    Any):


						"""simple docstring"""




						__UpperCAmelCase	: Any		=					data
						__UpperCAmelCase	: Node | None		=					None






class      a__				:


			def __init__(      self      :    Optional[int]):


						"""simple docstring"""




						__UpperCAmelCase	: Dict		=					None
						__UpperCAmelCase	: int		=					None


			def __iter__(      self      :    Optional[Any]):


						"""simple docstring"""




						__UpperCAmelCase	: List[Any]		=					self.head
						while self.head:
									yield node.data
									__UpperCAmelCase	: List[str]		=					node.next
									if node == self.head:
												break


			def __len__(      self      :    List[Any]):


						"""simple docstring"""




						return sum(1 for _ in self)


			def __repr__(      self      :    Any):


						"""simple docstring"""




						return "->".join(str(UpperCamelCase_) for item in iter(self))


			def       a_     (      self      :    int      ,  UpperCamelCase_      :    Any):


						"""simple docstring"""




						self.insert_nth(len(self)      ,  UpperCamelCase_)


			def       a_     (      self      :    Optional[int]      ,  UpperCamelCase_      :    Any):


						"""simple docstring"""




						self.insert_nth(0      ,  UpperCamelCase_)


			def       a_     (      self      :    int      ,  UpperCamelCase_      :    int      ,  UpperCamelCase_      :    Any):


						"""simple docstring"""




						if index < 0 or index > len(self):
									raise IndexError("list index out of range.")
						__UpperCAmelCase	: str		=					Node(UpperCamelCase_)
						if self.head is None:
									__UpperCAmelCase	: Dict		=					new_node  # first node points itself
									__UpperCAmelCase	: List[Any]		=					new_node
						elif index == 0:  # insert at head
									__UpperCAmelCase	: Optional[int]		=					self.head
									__UpperCAmelCase	: Optional[Any]		=					new_node
						else:
									__UpperCAmelCase	: Tuple		=					self.head
									for _ in range(index - 1):
												__UpperCAmelCase	: str		=					temp.next
									__UpperCAmelCase	: Dict		=					temp.next
									__UpperCAmelCase	: Tuple		=					new_node
									if index == len(self) - 1:  # insert at tail
												__UpperCAmelCase	: str		=					new_node


			def       a_     (      self      :    Optional[int]):


						"""simple docstring"""




						return self.delete_nth(0)


			def       a_     (      self      :    int):


						"""simple docstring"""




						return self.delete_nth(len(self) - 1)


			def       a_     (      self      :    Tuple      ,  UpperCamelCase_      :    int = 0):


						"""simple docstring"""




						if not 0 <= index < len(self):
									raise IndexError("list index out of range.")
						__UpperCAmelCase	: Any		=					self.head
						if self.head == self.tail:  # just one node
									__UpperCAmelCase	: Optional[int]		=					None
						elif index == 0:  # delete head node
									__UpperCAmelCase	: Union[str, Any]		=					self.tail.next.next
									__UpperCAmelCase	: Dict		=					self.head.next
						else:
									__UpperCAmelCase	: List[Any]		=					self.head
									for _ in range(index - 1):
												__UpperCAmelCase	: Any		=					temp.next
									__UpperCAmelCase	: Optional[int]		=					temp.next
									__UpperCAmelCase	: Dict		=					temp.next.next
									if index == len(self) - 1:  # delete at tail
												__UpperCAmelCase	: List[str]		=					temp
						return delete_node.data


			def       a_     (      self      :    Tuple):


						"""simple docstring"""




						return len(self) == 0






def 					_UpperCamelCase    (			)			->			None:


			"""simple docstring"""
			__UpperCAmelCase	: Optional[int]		=					CircularLinkedList()
			assert len(UpperCamelCase							) == 0
			assert circular_linked_list.is_empty() is True
			assert str(UpperCamelCase							) == ""

			try:
						circular_linked_list.delete_front()
						raise AssertionError  # This should not happen
			except IndexError:
						assert True  # This should happen

			try:
						circular_linked_list.delete_tail()
						raise AssertionError  # This should not happen
			except IndexError:
						assert True  # This should happen

			try:
						circular_linked_list.delete_nth(-1							)
						raise AssertionError
			except IndexError:
						assert True

			try:
						circular_linked_list.delete_nth(0							)
						raise AssertionError
			except IndexError:
						assert True

			assert circular_linked_list.is_empty() is True
			for i in range(5							):
						assert len(UpperCamelCase							) == i
						circular_linked_list.insert_nth(UpperCamelCase				,       i + 1							)
			assert str(UpperCamelCase							) == "->".join(str(UpperCamelCase							) for i in range(1				,       6							)							)

			circular_linked_list.insert_tail(6							)
			assert str(UpperCamelCase							) == "->".join(str(UpperCamelCase							) for i in range(1				,       7							)							)
			circular_linked_list.insert_head(0							)
			assert str(UpperCamelCase							) == "->".join(str(UpperCamelCase							) for i in range(0				,       7							)							)

			assert circular_linked_list.delete_front() == 0
			assert circular_linked_list.delete_tail() == 6
			assert str(UpperCamelCase							) == "->".join(str(UpperCamelCase							) for i in range(1				,       6							)							)
			assert circular_linked_list.delete_nth(2							) == 3

			circular_linked_list.insert_nth(2				,       3							)
			assert str(UpperCamelCase							) == "->".join(str(UpperCamelCase							) for i in range(1				,       6							)							)

			assert circular_linked_list.is_empty() is False


if __name__ == "__main__":
					import doctest

					doctest.testmod()








"""simple docstring"""





def 					_UpperCamelCase    (			UpperCamelCase				,       UpperCamelCase				,       UpperCamelCase							)			->			int:


			"""simple docstring"""

			if exponent == 1:
						return base
			if exponent % 2 == 0:
						__UpperCAmelCase	: Union[str, Any]		=					_modexpt(UpperCamelCase				,       exponent // 2				,       UpperCamelCase							) % modulo_value
						return (x * x) % modulo_value
			else:
						return (base * _modexpt(UpperCamelCase				,       exponent - 1				,       UpperCamelCase							)) % modulo_value

def 					_UpperCamelCase    (			UpperCamelCase = 1777				,       UpperCamelCase = 1855				,       UpperCamelCase = 8							)			->			int:


			"""simple docstring"""
			__UpperCAmelCase	: Optional[int]		=					base
			for _ in range(1				,       UpperCamelCase							):
						__UpperCAmelCase	: str		=					_modexpt(UpperCamelCase				,       UpperCamelCase				,       10**digits							)

			return result


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


