



"""simple docstring"""





def 	__lowerCAmelCase						(		__UpperCamelCase      :			int    ):


						'''simple docstring'''






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

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

						# Base case: C(0) = C(1) = 1
						snake_case_   : int						=			1
						if upper_limit > 0:
												snake_case_   : Optional[int]						=			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(__UpperCamelCase    ):
																		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       :					Union[str, Any]      					=					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						(		__UpperCamelCase      :			int					, __UpperCamelCase      :			int    ):


						'''simple docstring'''






						if a < 0 or b < 0:
												raise ValueError("""the value of both inputs must be positive"""    )

						snake_case_   : List[str]						=			str(bin(__UpperCamelCase    )    )[2:]  # remove the leading "0b"
						snake_case_   : Union[str, Any]						=			str(bin(__UpperCamelCase    )    )[2:]  # remove the leading "0b"

						snake_case_   : int						=			max(len(__UpperCamelCase    )					, len(__UpperCamelCase    )    )

						return "0b" + "".join(
						    str(int(char_a != char_b    )    )
						    for char_a, char_b in zip(a_binary.zfill(__UpperCamelCase    )					, b_binary.zfill(__UpperCamelCase    )    )    )


if __name__ == "__main__":
					import doctest

					doctest.testmod()

