
"""simple docstring"""






from __future__ import annotations

import math




def __magic_name__	(				_lowerCamelCase:		list,					_lowerCamelCase:		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'''			)
	lowerCAmelCase												=  [
	    [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 __magic_name__	(				_lowerCamelCase:		list,					_lowerCamelCase:		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 __magic_name__	(				_lowerCamelCase:		list,					_lowerCamelCase:		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 __magic_name__	(				_lowerCamelCase:		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!'''			)

	lowerCAmelCase												=  len(_lowerCamelCase			)
	lowerCAmelCase												=  matrix_length // 2

	lowerCAmelCase												=  [[a[i][j] for j in range(_lowerCamelCase,					_lowerCamelCase			)] for i in range(_lowerCamelCase			)]
	lowerCAmelCase												=  [
	    [a[i][j] for j in range(_lowerCamelCase,					_lowerCamelCase			)] for i in range(_lowerCamelCase,					_lowerCamelCase			)
	]

	lowerCAmelCase												=  [[a[i][j] for j in range(_lowerCamelCase			)] for i in range(_lowerCamelCase			)]
	lowerCAmelCase												=  [[a[i][j] for j in range(_lowerCamelCase			)] for i in range(_lowerCamelCase,					_lowerCamelCase			)]

	return top_left, top_right, bot_left, bot_right




def __magic_name__	(				_lowerCamelCase:		list			)					->						tuple[int, int]:

	'''simple docstring'''




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




def __magic_name__	(				_lowerCamelCase:		list			)					->						None:

	'''simple docstring'''




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




def __magic_name__	(				_lowerCamelCase:		list,					_lowerCamelCase:		list			)					->						list:

	'''simple docstring'''




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

	lowerCAmelCase							,       lowerCAmelCase							,       lowerCAmelCase							,       lowerCAmelCase												=  split_matrix(_lowerCamelCase			)
	lowerCAmelCase							,       lowerCAmelCase							,       lowerCAmelCase							,       lowerCAmelCase												=  split_matrix(_lowerCamelCase			)

	lowerCAmelCase												=  actual_strassen(_lowerCamelCase,					matrix_subtraction(_lowerCamelCase,					_lowerCamelCase			)			)
	lowerCAmelCase												=  actual_strassen(matrix_addition(_lowerCamelCase,					_lowerCamelCase			),					_lowerCamelCase			)
	lowerCAmelCase												=  actual_strassen(matrix_addition(_lowerCamelCase,					_lowerCamelCase			),					_lowerCamelCase			)
	lowerCAmelCase												=  actual_strassen(_lowerCamelCase,					matrix_subtraction(_lowerCamelCase,					_lowerCamelCase			)			)
	lowerCAmelCase												=  actual_strassen(matrix_addition(_lowerCamelCase,					_lowerCamelCase			),					matrix_addition(_lowerCamelCase,					_lowerCamelCase			)			)
	lowerCAmelCase												=  actual_strassen(matrix_subtraction(_lowerCamelCase,					_lowerCamelCase			),					matrix_addition(_lowerCamelCase,					_lowerCamelCase			)			)
	lowerCAmelCase												=  actual_strassen(matrix_subtraction(_lowerCamelCase,					_lowerCamelCase			),					matrix_addition(_lowerCamelCase,					_lowerCamelCase			)			)

	lowerCAmelCase												=  matrix_addition(matrix_subtraction(matrix_addition(_lowerCamelCase,					_lowerCamelCase			),					_lowerCamelCase			),					_lowerCamelCase			)
	lowerCAmelCase												=  matrix_addition(_lowerCamelCase,					_lowerCamelCase			)
	lowerCAmelCase												=  matrix_addition(_lowerCamelCase,					_lowerCamelCase			)
	lowerCAmelCase												=  matrix_subtraction(matrix_subtraction(matrix_addition(_lowerCamelCase,					_lowerCamelCase			),					_lowerCamelCase			),					_lowerCamelCase			)

	# construct the new matrix from our 4 quadrants
	lowerCAmelCase												=  []
	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 __magic_name__	(				_lowerCamelCase:		list,					_lowerCamelCase:		list			)					->						list:

	'''simple docstring'''




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

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

	lowerCAmelCase												=  max(*_lowerCamelCase,					*_lowerCamelCase			)
	lowerCAmelCase												=  int(math.pow(2,					math.ceil(math.loga(_lowerCamelCase			)			)			)			)
	lowerCAmelCase												=  matrixa
	lowerCAmelCase												=  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			)

	lowerCAmelCase												=  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__":
					UpperCAmelCase        =				[
					    [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],
					]
					UpperCAmelCase        =				[[0, 2, 1, 1], [1_6, 2, 3, 3], [2, 2, 7, 7], [1_3, 1_1, 2_2, 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() = }""")


