def    __lowerCamelCase	(		lowerCAmelCase__			,						lowerCAmelCase__			):
       lowerCAmelCase__  			=      []
       lowerCAmelCase__  			=      len(lowerCAmelCase__			)
       for i in range(lowerCAmelCase__			):
              lowerCAmelCase__  			=      []
              for j in range(lowerCAmelCase__			):
                     lowerCAmelCase__  			=      0
                     for k in range(lowerCAmelCase__			):
                            lowerCAmelCase__  			=      val + matrix_a[i][k] * matrix_b[k][j]
                     list_a.append(lowerCAmelCase__			)
              matrix_c.append(lowerCAmelCase__			)
       return matrix_c






def    __lowerCamelCase	(		lowerCAmelCase__			):
       return [[int(row == column			) for column in range(lowerCAmelCase__			)] for row in range(lowerCAmelCase__			)]






def    __lowerCamelCase	(		lowerCAmelCase__			):
       if n <= 1:
              return n
       lowerCAmelCase__  			=      identity(2			)
       lowerCAmelCase__  			=      [[1, 1], [1, 0]]
       lowerCAmelCase__  			=      n - 1
       while n > 0:
              if n % 2 == 1:
                     lowerCAmelCase__  			=      multiply(lowerCAmelCase__			,						lowerCAmelCase__			)
              lowerCAmelCase__  			=      multiply(lowerCAmelCase__			,						lowerCAmelCase__			)
              lowerCAmelCase__  			=      int(n / 2			)
       return res_matrix[0][0]






def    __lowerCamelCase	(		lowerCAmelCase__			):
       if n <= 1:
              return n
       lowerCAmelCase__  			=      0
       lowerCAmelCase__  			=      1
       for _ in range(2			,						n + 1			):
              lowerCAmelCase__			,      lowerCAmelCase__  			=      fiba, fiba + fiba
       return fiba






def    __lowerCamelCase	(		):
       for ordinal in "0th 1st 2nd 3rd 10th 100th 1000th".split():
              lowerCAmelCase__  			=      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    __lowerCamelCase	(		lowerCAmelCase__			):
       return " ".join([word[::-1] for word in input_str.split()]			)


if __name__ == "__main__":
    import doctest

    doctest.testmod()
