



def  lowercase    (				SCREAMING_SNAKE_CASE__    :		list[list[int]]			,    SCREAMING_SNAKE_CASE__    :		list[list[int]]			)					->       list[list[int]]:
 _snake_case      :					int					=   []
 _snake_case      :					Tuple					=   len(_lowerCamelCase			)
 for i in range(_lowerCamelCase			):
  _snake_case      :					List[str]					=   []
  for j in range(_lowerCamelCase			):
   _snake_case      :					Dict					=   0
   for k in range(_lowerCamelCase			):
    _snake_case      :					Any					=   val + matrix_a[i][k] * matrix_b[k][j]
   list_a.append(_lowerCamelCase			)
  matrix_c.append(_lowerCamelCase			)
 return matrix_c



def  lowercase    (				SCREAMING_SNAKE_CASE__    :		int			)					->       list[list[int]]:
 return [[int(row == column			) for column in range(_lowerCamelCase			)] for row in range(_lowerCamelCase			)]



def  lowercase    (				SCREAMING_SNAKE_CASE__    :		int			)					->       int:





 if n <= 1:
  return n
 _snake_case      :					Optional[Any]					=   identity(2			)
 _snake_case      :					Dict					=   [[1, 1], [1, 0]]
 _snake_case      :					Optional[Any]					=   n - 1
 while n > 0:
  if n % 2 == 1:
   _snake_case      :					str					=   multiply(_lowerCamelCase			,    _lowerCamelCase			)
  _snake_case      :					str					=   multiply(_lowerCamelCase			,    _lowerCamelCase			)
  _snake_case      :					int					=   int(n / 2			)
 return res_matrix[0][0]



def  lowercase    (				SCREAMING_SNAKE_CASE__    :		int			)					->       int:





 if n <= 1:
  return n
 _snake_case      :					Union[str, Any]					=   0
 _snake_case      :					Tuple					=   1
 for _ in range(2			,    n + 1			):
  _snake_case		,      _snake_case      :					Union[str, Any]					=   fiba, fiba + fiba
 return fiba



def  lowercase    (				)					->       None:





 for ordinal in "0th 1st 2nd 3rd 10th 100th 1000th".split():
  _snake_case      :					int					=   int("""""".join(c for c in ordinal if c in """0123456789"""			)			)  # 1000th --> 1000
  print(
      F'''{ordinal} fibonacci number using matrix exponentiation is '''
      F'''{nth_fibonacci_matrix(_lowerCamelCase			)} and using bruteforce is '''
      F'''{nth_fibonacci_bruteforce(_lowerCamelCase			)}\n'''			)
 # from timeit import timeit
 # print(timeit("nth_fibonacci_matrix(1000000)",
 #              "from main import nth_fibonacci_matrix", number=5))
 # print(timeit("nth_fibonacci_bruteforce(1000000)",
 #              "from main import nth_fibonacci_bruteforce", number=5))
 # 2.3342058970001744
 # 57.256506615000035


if __name__ == "__main__":
 import doctest

 doctest.testmod()
 main()





def  lowercase    (				SCREAMING_SNAKE_CASE__    :		int			)					->       int:
 if not isinstance(SCREAMING_SNAKE_CASE__			,    SCREAMING_SNAKE_CASE__			):
  raise TypeError("""recursive_lucas_number accepts only integer arguments."""			)
 if n_th_number == 0:
  return 2
 if n_th_number == 1:
  return 1

 return recursive_lucas_number(n_th_number - 1			) + recursive_lucas_number(
     n_th_number - 2			)



def  lowercase    (				SCREAMING_SNAKE_CASE__    :		int			)					->       int:
 if not isinstance(SCREAMING_SNAKE_CASE__			,    SCREAMING_SNAKE_CASE__			):
  raise TypeError("""dynamic_lucas_number accepts only integer arguments."""			)
 _snake_case		,      _snake_case      :					Any					=   2, 1
 for _ in range(SCREAMING_SNAKE_CASE__			):
  _snake_case		,      _snake_case      :					Union[str, Any]					=   b, a + b
 return a


if __name__ == "__main__":
  from doctest import testmod

  testmod()
  a__      =		int(input("""Enter the number of terms in lucas series:\n""").strip())
  print("""Using recursive function to calculate lucas series:""")
  print(""" """.join(str(recursive_lucas_number(i)) for i in range(n)))
  print("""\nUsing dynamic function to calculate lucas series:""")
  print(""" """.join(str(dynamic_lucas_number(i)) for i in range(n)))
