



from typing import TYPE_CHECKING

from ...utils import OptionalDependencyNotAvailable, _LazyModule, is_torch_available, is_vision_available


UpperCAmelCase__       =	{
    "configuration_bridgetower": [
        "BRIDGETOWER_PRETRAINED_CONFIG_ARCHIVE_MAP",
        "BridgeTowerConfig",
        "BridgeTowerTextConfig",
        "BridgeTowerVisionConfig",
    ],
    "processing_bridgetower": ["BridgeTowerProcessor"],
}

try:
							if not is_vision_available():
														raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
							pass
else:
							UpperCAmelCase__       =	["BridgeTowerImageProcessor"]

try:
							if not is_torch_available():
														raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
							pass
else:
							UpperCAmelCase__       =	[
							    "BRIDGETOWER_PRETRAINED_MODEL_ARCHIVE_LIST",
							    "BridgeTowerForContrastiveLearning",
							    "BridgeTowerForImageAndTextRetrieval",
							    "BridgeTowerForMaskedLM",
							    "BridgeTowerModel",
							    "BridgeTowerPreTrainedModel",
							]


if TYPE_CHECKING:
							from .configuration_bridgetower import (
							    BRIDGETOWER_PRETRAINED_CONFIG_ARCHIVE_MAP,
							    BridgeTowerConfig,
							    BridgeTowerTextConfig,
							    BridgeTowerVisionConfig,
							)
							from .processing_bridgetower import BridgeTowerProcessor

							try:
														if not is_vision_available():
																					raise OptionalDependencyNotAvailable()
							except OptionalDependencyNotAvailable:
														pass
							else:
														from .image_processing_bridgetower import BridgeTowerImageProcessor

							try:
														if not is_torch_available():
																					raise OptionalDependencyNotAvailable()
							except OptionalDependencyNotAvailable:
														pass
							else:
														from .modeling_bridgetower import (
														    BRIDGETOWER_PRETRAINED_MODEL_ARCHIVE_LIST,
														    BridgeTowerForContrastiveLearning,
														    BridgeTowerForImageAndTextRetrieval,
														    BridgeTowerForMaskedLM,
														    BridgeTowerModel,
														    BridgeTowerPreTrainedModel,
														)


else:
							import sys

							UpperCAmelCase__       =	_LazyModule(__name__, globals()["__file__"], _import_structure)





def 							A     (					_UpperCAmelCase    :       int   )    ->			"list[int]":







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

			_UpperCAmelCase			=       [0] * (upper_limit + 1)

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