def transpuesta(matriz):
  m = len(matriz)
  n = len(matriz[0])
  return [[matriz[j][i] for j in range(m)] for i in range(n)]

def producto_punto(vector1, vector2):
  return sum(vector1[i] * vector2[i] for i in range(len(vector1)))

def mult_mat(matriz1, matriz2):
  return [[producto_punto(fila, columna) for columna in transpuesta(matriz2)]
          for fila in matriz1]

def exp_log(a, n):
  if n == 0:
    return 1
  if n % 2 == 0:
    exp = exp_log(a, n // 2)
    return exp * exp
  return a * exp_log(a, n - 1)

def exp_mat(matriz, n):
  if n == 1:
    return matriz
  if n % 2 == 0:
    exp = exp_mat(matriz, n // 2)
    return mult_mat(exp, exp)
  return mult_mat(matriz, exp_mat(matriz, n - 1))




def g(n):
	if n<2:return 2
	return g(n-1)+g(n-2)

def gExpMat(n):
	if n<2:return 2
	
	coeficientes=[[1,1],[1,0]]
	
	cbases=[[2],[2]]
	
	return mult_mat( exp_mat(coeficientes,n-1),cbases)[0][0]

print(g(7))
print(gExpMat(7))