

'''simple docstring'''
from __future__ import annotations

import math


def  a__       (    _SCREAMING_SNAKE_CASE   :       list	,				_SCREAMING_SNAKE_CASE   :       list				)     ->					list:


	"""simple docstring"""





	if len(_lowerCamelCase				) != 2 or len(a[0]				) != 2 or len(_lowerCamelCase				) != 2 or len(b[0]				) != 2:
		raise Exception("Matrices are not 2x2"				)
	UpperCAmelCase_     :      Dict						=  [
	    [a[0][0] * b[0][0] + a[0][1] * b[1][0], a[0][0] * b[0][1] + a[0][1] * b[1][1]],
	    [a[1][0] * b[0][0] + a[1][1] * b[1][0], a[1][0] * b[0][1] + a[1][1] * b[1][1]],
	]
	return new_matrix


def  a__       (    _SCREAMING_SNAKE_CASE   :       list	,				_SCREAMING_SNAKE_CASE   :       list				)     ->					Optional[int]:


	"""simple docstring"""





	return [
	    [matrix_a[row][col] + matrix_b[row][col] for col in range(len(matrix_a[row]				)				)]
	    for row in range(len(_lowerCamelCase				)				)
	]


def  a__       (    _SCREAMING_SNAKE_CASE   :       list	,				_SCREAMING_SNAKE_CASE   :       list				)     ->					Optional[int]:


	"""simple docstring"""





	return [
	    [matrix_a[row][col] - matrix_b[row][col] for col in range(len(matrix_a[row]				)				)]
	    for row in range(len(_lowerCamelCase				)				)
	]


def  a__       (    _SCREAMING_SNAKE_CASE   :       list				)     ->					tuple[list, list, list, list]:


	"""simple docstring"""





	if len(_lowerCamelCase				) % 2 != 0 or len(a[0]				) % 2 != 0:
		raise Exception("Odd matrices are not supported!"				)

	UpperCAmelCase_     :      Union[str, Any]						=  len(_lowerCamelCase				)
	UpperCAmelCase_     :      List[Any]						=  matrix_length // 2

	UpperCAmelCase_     :      Any						=  [[a[i][j] for j in range(_lowerCamelCase	,				_lowerCamelCase				)] for i in range(_lowerCamelCase				)]
	UpperCAmelCase_     :      List[Any]						=  [
	    [a[i][j] for j in range(_lowerCamelCase	,				_lowerCamelCase				)] for i in range(_lowerCamelCase	,				_lowerCamelCase				)
	]

	UpperCAmelCase_     :      Optional[int]						=  [[a[i][j] for j in range(_lowerCamelCase				)] for i in range(_lowerCamelCase				)]
	UpperCAmelCase_     :      List[str]						=  [[a[i][j] for j in range(_lowerCamelCase				)] for i in range(_lowerCamelCase	,				_lowerCamelCase				)]

	return top_left, top_right, bot_left, bot_right


def  a__       (    _SCREAMING_SNAKE_CASE   :       list				)     ->					tuple[int, int]:


	"""simple docstring"""





	return len(_lowerCamelCase				), len(matrix[0]				)


def  a__       (    _SCREAMING_SNAKE_CASE   :       list				)     ->					None:


	"""simple docstring"""





	print("\n".join(str(_lowerCamelCase				) for line in matrix				)				)


def  a__       (    _SCREAMING_SNAKE_CASE   :       list	,				_SCREAMING_SNAKE_CASE   :       list				)     ->					list:


	"""simple docstring"""





	if matrix_dimensions(_lowerCamelCase				) == (2, 2):
		return default_matrix_multiplication(_lowerCamelCase	,				_lowerCamelCase				)

	UpperCAmelCase_					,					UpperCAmelCase_					,					UpperCAmelCase_					,					UpperCAmelCase_     :      Union[str, Any]						=  split_matrix(_lowerCamelCase				)
	UpperCAmelCase_					,					UpperCAmelCase_					,					UpperCAmelCase_					,					UpperCAmelCase_     :      Union[str, Any]						=  split_matrix(_lowerCamelCase				)

	UpperCAmelCase_     :      Optional[int]						=  actual_strassen(_lowerCamelCase	,				matrix_subtraction(_lowerCamelCase	,				_lowerCamelCase				)				)
	UpperCAmelCase_     :      Dict						=  actual_strassen(matrix_addition(_lowerCamelCase	,				_lowerCamelCase				)	,				_lowerCamelCase				)
	UpperCAmelCase_     :      Optional[int]						=  actual_strassen(matrix_addition(_lowerCamelCase	,				_lowerCamelCase				)	,				_lowerCamelCase				)
	UpperCAmelCase_     :      Optional[int]						=  actual_strassen(_lowerCamelCase	,				matrix_subtraction(_lowerCamelCase	,				_lowerCamelCase				)				)
	UpperCAmelCase_     :      str						=  actual_strassen(matrix_addition(_lowerCamelCase	,				_lowerCamelCase				)	,				matrix_addition(_lowerCamelCase	,				_lowerCamelCase				)				)
	UpperCAmelCase_     :      Optional[Any]						=  actual_strassen(matrix_subtraction(_lowerCamelCase	,				_lowerCamelCase				)	,				matrix_addition(_lowerCamelCase	,				_lowerCamelCase				)				)
	UpperCAmelCase_     :      Optional[Any]						=  actual_strassen(matrix_subtraction(_lowerCamelCase	,				_lowerCamelCase				)	,				matrix_addition(_lowerCamelCase	,				_lowerCamelCase				)				)

	UpperCAmelCase_     :      str						=  matrix_addition(matrix_subtraction(matrix_addition(_lowerCamelCase	,				_lowerCamelCase				)	,				_lowerCamelCase				)	,				_lowerCamelCase				)
	UpperCAmelCase_     :      List[Any]						=  matrix_addition(_lowerCamelCase	,				_lowerCamelCase				)
	UpperCAmelCase_     :      Union[str, Any]						=  matrix_addition(_lowerCamelCase	,				_lowerCamelCase				)
	UpperCAmelCase_     :      Optional[Any]						=  matrix_subtraction(matrix_subtraction(matrix_addition(_lowerCamelCase	,				_lowerCamelCase				)	,				_lowerCamelCase				)	,				_lowerCamelCase				)

	# construct the new matrix from our 4 quadrants
	UpperCAmelCase_     :      Dict						=  []
	for i in range(len(_lowerCamelCase				)				):
		new_matrix.append(top_left[i] + top_right[i]				)
	for i in range(len(_lowerCamelCase				)				):
		new_matrix.append(bot_left[i] + bot_right[i]				)
	return new_matrix


def  a__       (    _SCREAMING_SNAKE_CASE   :       list	,				_SCREAMING_SNAKE_CASE   :       list				)     ->					list:


	"""simple docstring"""





	if matrix_dimensions(_lowerCamelCase				)[1] != matrix_dimensions(_lowerCamelCase				)[0]:
		UpperCAmelCase_     :      Tuple						=  (
		    "Unable to multiply these matrices, please check the dimensions.\n"
		    F'''Matrix A: {matrixa}\n'''
		    F'''Matrix B: {matrixa}'''
		)
		raise Exception(_lowerCamelCase				)
	UpperCAmelCase_     :      List[str]						=  matrix_dimensions(_lowerCamelCase				)
	UpperCAmelCase_     :      int						=  matrix_dimensions(_lowerCamelCase				)

	if dimensiona[0] == dimensiona[1] and dimensiona[0] == dimensiona[1]:
		return [matrixa, matrixa]

	UpperCAmelCase_     :      Tuple						=  max(*_lowerCamelCase	,				*_lowerCamelCase				)
	UpperCAmelCase_     :      Any						=  int(math.pow(2	,				math.ceil(math.loga(_lowerCamelCase				)				)				)				)
	UpperCAmelCase_     :      Optional[Any]						=  matrixa
	UpperCAmelCase_     :      Tuple						=  matrixa

	# Adding zeros to the matrices so that the arrays dimensions are the same and also
	# power of 2
	for i in range(0	,				_lowerCamelCase				):
		if i < dimensiona[0]:
			for _ in range(dimensiona[1]	,				_lowerCamelCase				):
				new_matrixa[i].append(0				)
		else:
			new_matrixa.append([0] * maxim				)
		if i < dimensiona[0]:
			for _ in range(dimensiona[1]	,				_lowerCamelCase				):
				new_matrixa[i].append(0				)
		else:
			new_matrixa.append([0] * maxim				)

	UpperCAmelCase_     :      List[Any]						=  actual_strassen(_lowerCamelCase	,				_lowerCamelCase				)

	# Removing the additional zeros
	for i in range(0	,				_lowerCamelCase				):
		if i < dimensiona[0]:
			for _ in range(dimensiona[1]	,				_lowerCamelCase				):
				final_matrix[i].pop()
		else:
			final_matrix.pop()
	return final_matrix


if __name__ == "__main__":
					_lowerCamelCase      					=     [
					    [2, 3, 4, 5],
					    [6, 4, 3, 1],
					    [2, 3, 6, 7],
					    [3, 1, 2, 4],
					    [2, 3, 4, 5],
					    [6, 4, 3, 1],
					    [2, 3, 6, 7],
					    [3, 1, 2, 4],
					    [2, 3, 4, 5],
					    [6, 2, 3, 1],
					]
					_lowerCamelCase      					=     [[0, 2, 1, 1], [16, 2, 3, 3], [2, 2, 7, 7], [13, 11, 22, 4]]
					print(strassen(matrixa, matrixa))






"""simple docstring"""






from itertools import count




def __magic_name__	(				_lowerCamelCase:		int = 50			)					->						int:

	'''simple docstring'''




	lowerCAmelCase												=  [1] * min_block_length

	for n in count(_lowerCamelCase			):
		fill_count_functions.append(1			)

		for block_length in range(_lowerCamelCase,					n + 1			):
			for block_start in range(n - block_length			):
				fill_count_functions[n] += fill_count_functions[
				    n - block_start - block_length - 1
				]

			fill_count_functions[n] += 1

		if fill_count_functions[n] > 1_000_000:
			break

	return n


if __name__ == "__main__":
					print(f"""{solution() = }""")


