



"""simple docstring"""




import timeit


class 	a__		:


   def __init__(				self   :				Any,  lowerCAmelCase   :				str      )     ->							Union[str, Any]:
         if isinstance(lowerCAmelCase,  lowerCAmelCase      ):  # Initializes a matrix identical to the one provided.
               lowercase	:   Dict											= arg
               lowercase	:   int											= len(lowerCAmelCase      )
         else:  # Initializes a square matrix of the given size and set values to zero.
               lowercase	:   str											= arg
               lowercase	:   Any											= [[0 for _ in range(self.n      )] for _ in range(self.n      )]






   def __mul__(				self   :				Any,  lowerCAmelCase   :				Tuple      )     ->							Union[str, Any]:
         lowercase	:   Tuple											= Matrix(self.n      )
         for i in range(self.n      ):
               for j in range(self.n      ):
                     for k in range(self.n      ):
                           matrix.t[i][j] += self.t[i][k] * b.t[k][j]
         return matrix




def 	lowercase__  (      _UpperCAmelCase						,   _UpperCAmelCase					)  ->      List[Any]:






      '''simple docstring'''


      lowercase	:   List[Any]											= Matrix([[1, 0], [0, 1]]					)
      while b > 0:
            if b & 1:
                  matrix *= a
            a *= a
            b >>= 1
      return matrix


def 	lowercase__  (      _UpperCAmelCase						,   _UpperCAmelCase						,   _UpperCAmelCase					)  ->      Union[str, Any]:






      '''simple docstring'''


      if n == 1:
            return fa
      elif n == 2:
            return fa
      lowercase	:   Tuple											= Matrix([[1, 1], [1, 0]]					)
      lowercase	:   Optional[Any]											= modular_exponentiation(_UpperCAmelCase						,   n - 2					)
      return fa * matrix.t[0][0] + fa * matrix.t[0][1]


def 	lowercase__  (      _UpperCAmelCase						,   _UpperCAmelCase						,   _UpperCAmelCase					)  ->      List[str]:






      '''simple docstring'''


      if n == 1:
            return fa
      elif n == 2:
            return fa

      lowercase	:   List[Any]											= fa
      lowercase	:   List[str]											= fa
      n -= 2

      while n > 0:
            lowercase						,     lowercase	:   Optional[Any]											= fn_a + fn_a, fn_a
            n -= 1

      return fn_a


def 	lowercase__  (      )  ->      int:






      '''simple docstring'''


      lowercase	:   List[Any]											= '\nfrom random import randint\nfrom __main__ import fibonacci_with_matrix_exponentiation\n'
      lowercase	:   str											= 'fibonacci_with_matrix_exponentiation(randint(1,70000), 1, 1)'
      lowercase	:   Optional[Any]											= timeit.timeit(setup=_UpperCAmelCase						,   stmt=_UpperCAmelCase						,   number=1_00					)
      print('With matrix exponentiation the average execution time is '						,   exec_time / 1_00					)
      return exec_time


def 	lowercase__  (      )  ->      List[str]:






      '''simple docstring'''


      lowercase	:   str											= '\nfrom random import randint\nfrom __main__ import simple_fibonacci\n'
      lowercase	:   Optional[Any]											= 'simple_fibonacci(randint(1,70000), 1, 1)'
      lowercase	:   Any											= timeit.timeit(setup=_UpperCAmelCase						,   stmt=_UpperCAmelCase						,   number=1_00					)
      print(
          'Without matrix exponentiation the average execution time is '						,   exec_time / 1_00					)
      return exec_time


def 	lowercase__  (      )  ->      Dict:






      '''simple docstring'''


      matrix_exponentiation_time()
      simple_fibonacci_time()


if __name__ == "__main__":
     main()





"""simple docstring"""




from __future__ import annotations

from typing import Generic, TypeVar

_UpperCamelCase:					str     				=	TypeVar('T')


class 	a__		(    Generic[T]  ):


   def __init__(				self   :				Optional[int],  lowerCAmelCase   :				T      )     ->							List[Any]:
         lowercase	:   Optional[int]											= data  # Assign data
         lowercase	:   Node[T] | None											= None  # Initialize next as null
         lowercase	:   Node[T] | None											= None  # Initialize prev as null




class 	a__		(    Generic[T]  ):


   def __init__(				self   :				Optional[int]      )     ->							None:
         lowercase	:   Node[T] | None											= None


   def 							lowercase					(				self   :				Any,  lowerCAmelCase   :				T      )     ->							None:
         if self.head is None:
               lowercase	:   Tuple											= Node(lowerCAmelCase      )
         else:
               lowercase	:   Dict											= Node(lowerCAmelCase      )
               lowercase	:   str											= new_node
               lowercase	:   int											= self.head
               lowercase	:   List[str]											= None
               lowercase	:   List[str]											= new_node


   def 							lowercase					(				self   :				Dict      )     ->							T | None:
         if self.head is None:
               return None
         else:
               assert self.head is not None
               lowercase	:   Optional[int]											= self.head.data
               lowercase	:   Any											= self.head.next
               if self.head is not None:
                     lowercase	:   Optional[Any]											= None
               return temp


   def 							lowercase					(				self   :				List[Any]      )     ->							T | None:
         return self.head.data if self.head is not None else None


   def __len__(				self   :				int      )     ->							int:
         lowercase	:   Any											= self.head
         lowercase	:   List[Any]											= 0
         while temp is not None:
               count += 1
               lowercase	:   Any											= temp.next
         return count


   def 							lowercase					(				self   :				List[Any]      )     ->							bool:
         return self.head is None






   def 							lowercase					(				self   :				Optional[int]      )     ->							None:
         print('stack elements are:'      )
         lowercase	:   Optional[int]											= self.head
         while temp is not None:
               print(temp.data,  end='->'      )
               lowercase	:   List[str]											= temp.next


# Code execution starts here
if __name__ == "__main__":
     # Start with the empty stack
     _UpperCamelCase:					Stack[int]     				=	Stack()

     # Insert 4 at the beginning. So stack becomes 4->None
     print('Stack operations using Doubly LinkedList')
     stack.push(4)

     # Insert 5 at the beginning. So stack becomes 4->5->None
     stack.push(5)

     # Insert 6 at the beginning. So stack becomes 4->5->6->None
     stack.push(6)

     # Insert 7 at the beginning. So stack becomes 4->5->6->7->None
     stack.push(7)

     # Print the stack
     stack.print_stack()

     # Print the top element
     print('\nTop element is ', stack.top())

     # Print the stack size
     print('Size of the stack is ', len(stack))

     # pop the top element
     stack.pop()

     # pop the top element
     stack.pop()

     # two elements have now been popped off
     stack.print_stack()

     # Print True if the stack is empty else False
     print('\nstack is empty:', stack.is_empty())
