Matrix Exponentiation Algorithm

Matrix Exponentiation.py

#!/usr/bin/env python3

def multiply(x, y):
	"""
	x is a 2x2 matrix
	y is either a 2x1 matrix or 2x2 matrix
	
	x -> [0, 1, 
	      2, 3]
	y -> [0, 
	      1] 
	      or 
	      [0, 1, 
	       2, 3]
	"""

	# y = 2x1 matrix
	if (len(y) == 2):
		a = x[0]*y[0] + x[1]*y[1]
		b = x[2]*y[0] + x[3]*y[1]

		return [a, b]

	# y = 2x2 matrix
	elif (len(y) == 4):
		a = x[0]*y[0] + x[1]*y[2]
		b = x[0]*y[1] + x[1]*y[3]
		c = x[2]*y[0] + x[3]*y[2]
		d = x[2]*y[1] + x[3]*y[3]

		return [a, b, c, d]

def matrix_expo(x, n):
	if n == 1:
		return x
	if n % 2 == 0:
		return matrix_expo(multiply(x, x), n // 2)
	return multiply(x, matrix_expo(multiply(x, x), n // 2))

a = [1, 1, 1, 0]
v = [1, 0]

x = int(input())

print(multiply(matrix_expo(a, x-1), v)[0])