


'''simple docstring'''


def        __lowerCAmelCase       (__lowerCAmelCase      ):
		if upper_limit < 0:
				raise ValueError("Limit for the Catalan sequence must be ≥ 0"      )

		_UpperCAmelCase						:				int	    =					[0] * (upper_limit + 1)

		# Base case: C(0) = C(1) = 1
		_UpperCAmelCase						:				int	    =					1
		if upper_limit > 0:
				_UpperCAmelCase						:				Optional[Any]	    =					1

		# Recurrence relation: C(i) = sum(C(j).C(i-j-1)), from j = 0 to i
		for i in range(2					,       upper_limit + 1      ):
				for j in range(__lowerCAmelCase      ):
						catalan_list[i] += catalan_list[j] * catalan_list[i - j - 1]

		return catalan_list


if __name__ == "__main__":
						print('\n********* Catalan Numbers Using Dynamic Programming ************\n')
						print('\n*** Enter -1 at any time to quit ***')
						print('\nEnter the upper limit (≥ 0) for the Catalan number sequence: ', end='')
						try:
												while True:
																		lowerCamelCase__					=   int(input().strip())
																		if N < 0:
																								print('\n********* Goodbye!! ************')
																								break
																		else:
																								print(F'''The Catalan numbers from 0 through {N} are:''')
																								print(catalan_numbers(N))
																								print('Try another upper limit for the sequence: ', end='')
						except (NameError, ValueError):
												print('\n********* Invalid input, goodbye! ************\n')

						import doctest

						doctest.testmod()







'''simple docstring'''


def        __lowerCAmelCase       (__lowerCAmelCase = 50      ):
		_UpperCAmelCase						:				Tuple	    =					[[0] * 3 for _ in range(length + 1      )]

		for row_length in range(length + 1      ):
				for tile_length in range(2					,       5      ):
						for tile_start in range(row_length - tile_length + 1      ):
								different_colour_ways_number[row_length][tile_length - 2] += (
								    different_colour_ways_number[row_length - tile_start - tile_length][
								        tile_length - 2
								    ]
								    + 1
								)

		return sum(different_colour_ways_number[length]      )


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



