
def      lowerCamelCase__       (       __lowerCAmelCase						:						list[list[int]]					,							__lowerCAmelCase						:						int					,							__lowerCAmelCase						:						int					,							__lowerCAmelCase						:						set       ):




			"""simple docstring"""


			lowerCAmelCase_			,						lowerCAmelCase_      			=			len(__lowerCAmelCase       ), len(grid[0]       )
			if (
			    min(__lowerCAmelCase					,							__lowerCAmelCase       ) < 0
			    or row == row_length
			    or col == col_length
			    or (row, col) in visit
			    or grid[row][col] == 1
			):
						return 0
			if row == row_length - 1 and col == col_length - 1:
						return 1

			visit.add((row, col)       )

			lowerCAmelCase_      			=			0
			count += depth_first_search(__lowerCAmelCase					,							row + 1					,							__lowerCAmelCase					,							__lowerCAmelCase       )
			count += depth_first_search(__lowerCAmelCase					,							row - 1					,							__lowerCAmelCase					,							__lowerCAmelCase       )
			count += depth_first_search(__lowerCAmelCase					,							__lowerCAmelCase					,							col + 1					,							__lowerCAmelCase       )
			count += depth_first_search(__lowerCAmelCase					,							__lowerCAmelCase					,							col - 1					,							__lowerCAmelCase       )

			visit.remove((row, col)       )
			return count


if __name__ == "__main__":
			import doctest

			doctest.testmod()





def      lowerCamelCase__       (       __lowerCAmelCase						:						int       ):




			"""simple docstring"""


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

			lowerCAmelCase_      			=			[0] * (upper_limit + 1)

			# Base case: C(0) = C(1) = 1
			lowerCAmelCase_      			=			1
			if upper_limit > 0:
						lowerCAmelCase_      			=			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:
									_A     =  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()



