
'''simple docstring'''
import timeit







class 			__A					:
 def __init__( self      :     Any					, lowerCamelCase      :     Optional[Any]							):



   """simple docstring"""





   if isinstance(lowerCamelCase					, lowerCamelCase							):  # Initializes a matrix identical to the one provided.
     __A		:  Optional[Any]       				=		arg
     __A		:  Tuple       				=		len(lowerCamelCase							)
   else:  # Initializes a square matrix of the given size and set values to zero.
     __A		:  Dict       				=		arg
     __A		:  Union[str, Any]       				=		[[0 for _ in range(self.n							)] for _ in range(self.n							)]






 def __mul__( self      :     List[Any]					, lowerCamelCase      :     Optional[Any]							):



   """simple docstring"""





   __A		:  Optional[Any]       				=		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 							A_  (    __SCREAMING_SNAKE_CASE    :	Any      ,  __SCREAMING_SNAKE_CASE    :	Dict			)					->							Union[str, Any]:





  """simple docstring"""

  __A		:  Dict       				=		Matrix([[1, 0], [0, 1]]			)
  while b > 0:
    if b & 1:
      matrix *= a
    a *= a
    b >>= 1
  return matrix







def 							A_  (    __SCREAMING_SNAKE_CASE    :	Optional[Any]      ,  __SCREAMING_SNAKE_CASE    :	List[str]      ,  __SCREAMING_SNAKE_CASE    :	List[Any]			)					->							Any:





  """simple docstring"""

  if n == 1:
    return fa
  elif n == 2:
    return fa
  __A		:  List[Any]       				=		Matrix([[1, 1], [1, 0]]			)
  __A		:  Union[str, Any]       				=		modular_exponentiation(__SCREAMING_SNAKE_CASE      ,  n - 2			)
  return fa * matrix.t[0][0] + fa * matrix.t[0][1]







def 							A_  (    __SCREAMING_SNAKE_CASE    :	Union[str, Any]      ,  __SCREAMING_SNAKE_CASE    :	int      ,  __SCREAMING_SNAKE_CASE    :	Any			)					->							int:





  """simple docstring"""

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

  __A		:  Any       				=		fa
  __A		:  Tuple       				=		fa
  n -= 2

  while n > 0:
    __A				,       __A		:  str       				=		fn_a + fn_a, fn_a
    n -= 1

  return fn_a







def 							A_  (    )					->							int:





  """simple docstring"""

  __A		:  Tuple       				=		"""
from random import randint
from __main__ import fibonacci_with_matrix_exponentiation
"""
  __A		:  str       				=		"""fibonacci_with_matrix_exponentiation(randint(1,70000), 1, 1)"""
  __A		:  Tuple       				=		timeit.timeit(setup=__SCREAMING_SNAKE_CASE      ,  stmt=__SCREAMING_SNAKE_CASE      ,  number=100			)
  print("""With matrix exponentiation the average execution time is """      ,  exec_time / 100			)
  return exec_time







def 							A_  (    )					->							Dict:





  """simple docstring"""

  __A		:  List[Any]       				=		"""
from random import randint
from __main__ import simple_fibonacci
"""
  __A		:  str       				=		"""simple_fibonacci(randint(1,70000), 1, 1)"""
  __A		:  Any       				=		timeit.timeit(setup=__SCREAMING_SNAKE_CASE      ,  stmt=__SCREAMING_SNAKE_CASE      ,  number=100			)
  print(
      """Without matrix exponentiation the average execution time is """      ,  exec_time / 100			)
  return exec_time







def 							A_  (    )					->							Optional[int]:





  """simple docstring"""

  matrix_exponentiation_time()
  simple_fibonacci_time()


if __name__ == "__main__":
     main()





'''simple docstring'''
from __future__ import annotations







def 							A_  (    __SCREAMING_SNAKE_CASE    :	float | int      ,  __SCREAMING_SNAKE_CASE    :	float | int      ,  __SCREAMING_SNAKE_CASE    :	float | int      ,  )					->							list[float | int]:





  """simple docstring"""

  if not all((nth_term, start_term_a, common_ratio_r)			):
    return []
  __A		:  list[float | int]       				=		[]
  __A		:  Union[str, Any]       				=		1
  __A		:  List[str]       				=		common_ratio_r
  for _ in range(int(__SCREAMING_SNAKE_CASE			)			):
    if not series:
      series.append(__SCREAMING_SNAKE_CASE			)
    else:
      power += 1
      series.append(float(start_term_a * multiple			)			)
      __A		:  List[str]       				=		pow(float(__SCREAMING_SNAKE_CASE			)      ,  __SCREAMING_SNAKE_CASE			)
  return series


if __name__ == "__main__":
     import doctest

     doctest.testmod()

     A__ :		Optional[int]					=float(input('Enter the last number (n term) of the Geometric Series'))
     A__ :		List[Any]					=float(input('Enter the starting term (a) of the Geometric Series'))
     A__ :		List[Any]					=float(
         input('Enter the common ratio between two terms (r) of the Geometric Series')
     )
     print('Formula of Geometric Series => a + ar + ar^2 ... +ar^n')
     print(geometric_series(nth_term, start_term_a, common_ratio_r))



