


'''simple docstring'''







import timeit
class  lowercase_					:


    def __init__(					self  , a   ):
          if isinstance(a  , a   ):  # Initializes a matrix identical to the one provided.
                UpperCamelCase__  =    arg
                UpperCamelCase__  =    len(a   )
          else:  # Initializes a square matrix of the given size and set values to zero.
                UpperCamelCase__  =    arg
                UpperCamelCase__  =    [[0 for _ in range(self.n   )] for _ in range(self.n   )]


    def __mul__(					self  , a   ):
          UpperCamelCase__  =    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 _UpperCamelCase	(					__A				,      __A   )							->		List[str]:


      '''simple docstring'''



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







def _UpperCamelCase	(					__A				,      __A				,      __A   )							->		Tuple:


      '''simple docstring'''



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







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


      '''simple docstring'''



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

      UpperCamelCase__  =    fa
      UpperCamelCase__  =    fa
      n -= 2

      while n > 0:
            UpperCamelCase__ ,     UpperCamelCase__  =    fn_a + fn_a, fn_a
            n -= 1

      return fn_a







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


      '''simple docstring'''



      UpperCamelCase__  =    "\nfrom random import randint\nfrom __main__ import fibonacci_with_matrix_exponentiation\n"
      UpperCamelCase__  =    "fibonacci_with_matrix_exponentiation(randint(1,70000), 1, 1)"
      UpperCamelCase__  =    timeit.timeit(setup=__A				,      stmt=__A				,      number=100   )
      print("With matrix exponentiation the average execution time is "				,      exec_time / 100   )
      return exec_time







def _UpperCamelCase	(					)							->		str:


      '''simple docstring'''



      UpperCamelCase__  =    "\nfrom random import randint\nfrom __main__ import simple_fibonacci\n"
      UpperCamelCase__  =    "simple_fibonacci(randint(1,70000), 1, 1)"
      UpperCamelCase__  =    timeit.timeit(setup=__A				,      stmt=__A				,      number=100   )
      print(
          "Without matrix exponentiation the average execution time is "				,      exec_time / 100   )
      return exec_time







def _UpperCamelCase	(					)							->		str:


      '''simple docstring'''



      matrix_exponentiation_time()
      simple_fibonacci_time()


if __name__ == "__main__":
  main()









'''simple docstring'''







def _UpperCamelCase	(					__A   )							->		int:


      '''simple docstring'''



      if number != int(__A   ):
            raise ValueError("factorial() only accepts integral values"   )
      if number < 0:
            raise ValueError("factorial() not defined for negative values"   )
      UpperCamelCase__  =    1
      for i in range(1				,      number + 1   ):
            value *= i
      return value







def _UpperCamelCase	(					__A   )							->		int:


      '''simple docstring'''



      if not isinstance(__A				,      __A   ):
            raise ValueError("factorial() only accepts integral values"   )
      if n < 0:
            raise ValueError("factorial() not defined for negative values"   )
      return 1 if n == 0 or n == 1 else n * factorial(n - 1   )


if __name__ == "__main__":
  import doctest

  doctest.testmod()

  a__  : str				=	int(input('Enter a positive integer: ').strip() or 0)
  print(F"""factorial{n} is {factorial(n)}""")





