



"""simple docstring"""





import re
from typing import Callable, List, Optional, Union

import tensorflow as tf


try:
					from tensorflow.keras.optimizers.legacy import Adam
except ImportError:
					from tensorflow.keras.optimizers import Adam



class    _lowerCAmelCase    (				tf.keras.optimizers.schedules.LearningRateSchedule		):





		"""simple docstring"""






		def __init__(					self							,    _lowercase							,    _lowercase							,    _lowercase							,    _lowercase = 1.0							,    _lowercase = None							,    ) ->						int:







								'''simple docstring'''

								super().__init__()
								snake_case_   : Optional[int]						=			initial_learning_rate
								snake_case_   : Optional[Any]						=			warmup_steps
								snake_case_   : Optional[Any]						=			power
								snake_case_   : int						=			decay_schedule_fn
								snake_case_   : Dict						=			name





		def __call__(					self							,    _lowercase   ) ->						str:







								'''simple docstring'''

								with tf.name_scope(self.name or """WarmUp"""   ) as name:
														# Implements polynomial warmup. i.e., if global_step < warmup_steps, the
														# learning rate will be `global_step/num_warmup_steps * init_lr`.
														snake_case_   : Optional[Any]						=			tf.cast(__lowerCAmelCase							,    tf.floataa   )
														snake_case_   : Dict						=			tf.cast(self.warmup_steps							,    tf.floataa   )
														snake_case_   : Optional[Any]						=			global_step_float / warmup_steps_float
														snake_case_   : List[Any]						=			self.initial_learning_rate * tf.math.pow(__lowerCAmelCase							,    self.power   )
														return tf.cond(
														    global_step_float < warmup_steps_float							,    lambda: warmup_learning_rate							,    lambda: self.decay_schedule_fn(step - self.warmup_steps   )							,    name=__lowerCAmelCase							,    )





		def    UpperCAmelCase__							(					self   ) ->						Union[str, Any]:







								'''simple docstring'''

								return {
								    "initial_learning_rate": self.initial_learning_rate,
								    "decay_schedule_fn": self.decay_schedule_fn,
								    "warmup_steps": self.warmup_steps,
								    "power": self.power,
								    "name": self.name,
								}




def 	__lowerCAmelCase						(		__UpperCamelCase      :			Optional[int]					, __UpperCamelCase      :			Any					, __UpperCamelCase      :			Optional[Any]					, __UpperCamelCase      :			Optional[Any] = 0.0					, __UpperCamelCase      :			int = 0.9					, __UpperCamelCase      :			str = 0.999					, __UpperCamelCase      :			Dict = 1E-8					, __UpperCamelCase      :			Union[str, Any] = None					, __UpperCamelCase      :			List[Any] = None					, __UpperCamelCase      :			Optional[int] = 0.0					, __UpperCamelCase      :			str = 1.0					, __UpperCamelCase      :			Optional[Any] = None					, ):


						'''simple docstring'''






						snake_case_   : List[str]						=			tf.keras.optimizers.schedules.PolynomialDecay(
						    initial_learning_rate=__snake_case					, decay_steps=num_train_steps - num_warmup_steps					, end_learning_rate=init_lr * min_lr_ratio					, power=__snake_case					, )
						if num_warmup_steps:
												snake_case_   : Tuple						=			WarmUp(
												    initial_learning_rate=__snake_case					, decay_schedule_fn=__snake_case					, warmup_steps=__snake_case					, )
						if weight_decay_rate > 0.0:
												snake_case_   : Dict						=			AdamWeightDecay(
												    learning_rate=__snake_case					, weight_decay_rate=__snake_case					, beta_a=__snake_case					, beta_a=__snake_case					, epsilon=__snake_case					, clipnorm=__snake_case					, global_clipnorm=__snake_case					, exclude_from_weight_decay=["""LayerNorm""", """layer_norm""", """bias"""]					, include_in_weight_decay=__snake_case					, )
						else:
												snake_case_   : Any						=			tf.keras.optimizers.Adam(
												    learning_rate=__snake_case					, beta_a=__snake_case					, beta_a=__snake_case					, epsilon=__snake_case					, clipnorm=__snake_case					, global_clipnorm=__snake_case					, )
						# We return the optimizer and the LR scheduler in order to better track the
						# evolution of the LR independently of the optimizer.
						return optimizer, lr_schedule



class    _lowerCAmelCase    (				SCREAMING_SNAKE_CASE__		):





		"""simple docstring"""






		def __init__(					self							,    _lowercase = 0.001							,    _lowercase = 0.9							,    _lowercase = 0.999							,    _lowercase = 1E-7							,    _lowercase = False							,    _lowercase = 0.0							,    _lowercase = None							,    _lowercase = None							,    _lowercase = "AdamWeightDecay"							,    **_lowercase							,    ) ->						int:







								'''simple docstring'''

								super().__init__(__lowerCAmelCase							,    __lowerCAmelCase							,    __lowerCAmelCase							,    __lowerCAmelCase							,    __lowerCAmelCase							,    __lowerCAmelCase							,    **__lowerCAmelCase   )
								snake_case_   : Optional[int]						=			weight_decay_rate
								snake_case_   : List[Any]						=			include_in_weight_decay
								snake_case_   : Union[str, Any]						=			exclude_from_weight_decay





		@classmethod
		def    UpperCAmelCase__							(					cls							,    _lowercase   ) ->						List[Any]:







								'''simple docstring'''

								snake_case_   : Any						=			{"""WarmUp""": WarmUp}
								return super(__lowerCAmelCase							,    cls   ).from_config(__lowerCAmelCase							,    custom_objects=__lowerCAmelCase   )





		def    UpperCAmelCase__							(					self							,    _lowercase							,    _lowercase							,    _lowercase   ) ->						Dict:







								'''simple docstring'''

								super(__lowerCAmelCase							,    self   )._prepare_local(__lowerCAmelCase							,    __lowerCAmelCase							,    __lowerCAmelCase   )
								snake_case_   : Union[str, Any]						=			tf.constant(
								    self.weight_decay_rate							,    name="""adam_weight_decay_rate"""   )





		def    UpperCAmelCase__							(					self							,    _lowercase							,    _lowercase							,    _lowercase   ) ->						Dict:







								'''simple docstring'''

								snake_case_   : Dict						=			self._do_use_weight_decay(var.name   )
								if do_decay:
														return var.assign_sub(
														    learning_rate * var * apply_state[(var.device, var.dtype.base_dtype)]["""weight_decay_rate"""]							,    use_locking=self._use_locking							,    )
								return tf.no_op()





		def    UpperCAmelCase__							(					self							,    _lowercase							,    _lowercase=None							,    **_lowercase   ) ->						Any:







								'''simple docstring'''

								snake_case_			,		snake_case_   : str						=			list(zip(*__lowerCAmelCase   )   )
								return super(__lowerCAmelCase							,    self   ).apply_gradients(zip(__lowerCAmelCase							,    __lowerCAmelCase   )							,    name=__lowerCAmelCase							,    **__lowerCAmelCase   )





		def    UpperCAmelCase__							(					self							,    _lowercase							,    _lowercase							,    _lowercase   ) ->						List[str]:







								'''simple docstring'''

								if apply_state is None:
														return self._decayed_lr_t[var_dtype], {}

								snake_case_   : Optional[int]						=			apply_state or {}
								snake_case_   : Union[str, Any]						=			apply_state.get((var_device, var_dtype)   )
								if coefficients is None:
														snake_case_   : Optional[int]						=			self._fallback_apply_state(__lowerCAmelCase							,    __lowerCAmelCase   )
														snake_case_   : Optional[Any]						=			coefficients

								return coefficients["lr_t"], {"apply_state": apply_state}





		def    UpperCAmelCase__							(					self							,    _lowercase							,    _lowercase							,    _lowercase=None   ) ->						Union[str, Any]:







								'''simple docstring'''

								snake_case_			,		snake_case_   : List[str]						=			self._get_lr(var.device							,    var.dtype.base_dtype							,    __lowerCAmelCase   )
								snake_case_   : Union[str, Any]						=			self._decay_weights_op(__lowerCAmelCase							,    __lowerCAmelCase							,    __lowerCAmelCase   )
								with tf.control_dependencies([decay]   ):
														return super(__lowerCAmelCase							,    self   )._resource_apply_dense(__lowerCAmelCase							,    __lowerCAmelCase							,    **__lowerCAmelCase   )





		def    UpperCAmelCase__							(					self							,    _lowercase							,    _lowercase							,    _lowercase							,    _lowercase=None   ) ->						List[Any]:







								'''simple docstring'''

								snake_case_			,		snake_case_   : Union[str, Any]						=			self._get_lr(var.device							,    var.dtype.base_dtype							,    __lowerCAmelCase   )
								snake_case_   : int						=			self._decay_weights_op(__lowerCAmelCase							,    __lowerCAmelCase							,    __lowerCAmelCase   )
								with tf.control_dependencies([decay]   ):
														return super(__lowerCAmelCase							,    self   )._resource_apply_sparse(__lowerCAmelCase							,    __lowerCAmelCase							,    __lowerCAmelCase							,    **__lowerCAmelCase   )





		def    UpperCAmelCase__							(					self   ) ->						str:







								'''simple docstring'''

								snake_case_   : str						=			super().get_config()
								config.update({"""weight_decay_rate""": self.weight_decay_rate}   )
								return config





		def    UpperCAmelCase__							(					self							,    _lowercase   ) ->						List[str]:







								'''simple docstring'''

								if self.weight_decay_rate == 0:
														return False

								if self._include_in_weight_decay:
														for r in self._include_in_weight_decay:
																				if re.search(__lowerCAmelCase							,    __lowerCAmelCase   ) is not None:
																										return True

								if self._exclude_from_weight_decay:
														for r in self._exclude_from_weight_decay:
																				if re.search(__lowerCAmelCase							,    __lowerCAmelCase   ) is not None:
																										return False
								return True




class    _lowerCAmelCase    (				SCREAMING_SNAKE_CASE__		):





		"""simple docstring"""






		def __init__(					self   ) ->						Any:







								'''simple docstring'''

								snake_case_   : List[Any]						=			[]
								snake_case_   : Union[str, Any]						=			None





		@property
		def    UpperCAmelCase__							(					self   ) ->						List[str]:







								'''simple docstring'''

								if self._accum_steps is None:
														snake_case_   : str						=			tf.Variable(
														    tf.constant(0							,    dtype=tf.intaa   )							,    trainable=__lowerCAmelCase							,    synchronization=tf.VariableSynchronization.ON_READ							,    aggregation=tf.VariableAggregation.ONLY_FIRST_REPLICA							,    )

								return self._accum_steps.value()





		@property
		def    UpperCAmelCase__							(					self   ) ->						Any:







								'''simple docstring'''

								if not self._gradients:
														raise ValueError("""The accumulator should be called first to initialize the gradients"""   )
								return [gradient.value() if gradient is not None else gradient for gradient in self._gradients]





		def __call__(					self							,    _lowercase   ) ->						int:







								'''simple docstring'''

								if not self._gradients:
														snake_case_   : str						=			self.step  # Create the step variable.
														self._gradients.extend(
														    [
														        tf.Variable(
														            tf.zeros_like(__lowerCAmelCase   )							,    trainable=__lowerCAmelCase							,    synchronization=tf.VariableSynchronization.ON_READ							,    aggregation=tf.VariableAggregation.ONLY_FIRST_REPLICA							,    )
														        if gradient is not None
														        else gradient
														        for gradient in gradients
														    ]   )
								if len(__lowerCAmelCase   ) != len(self._gradients   ):
														raise ValueError(f'Expected {len(self._gradients   )} gradients, but got {len(__lowerCAmelCase   )}'   )

								for accum_gradient, gradient in zip(self._gradients							,    __lowerCAmelCase   ):
														if accum_gradient is not None and gradient is not None:
																				accum_gradient.assign_add(__lowerCAmelCase   )

								self._accum_steps.assign_add(1   )





		def    UpperCAmelCase__							(					self   ) ->						Union[str, Any]:







								'''simple docstring'''

								if not self._gradients:
														return
								self._accum_steps.assign(0   )
								for gradient in self._gradients:
														if gradient is not None:
																				gradient.assign(tf.zeros_like(__lowerCAmelCase   )   )






"""simple docstring"""





def 	__lowerCAmelCase						(		__UpperCamelCase      :			int					, __UpperCamelCase      :			int    ):


						'''simple docstring'''






						snake_case_   : Any						=			1  # To kept the Calculated Value
						# Since C(n, k) = C(n, n-k)
						if k > (n - k):
												snake_case_   : Optional[int]						=			n - k
						# Calculate C(n,k)
						for i in range(__UpperCamelCase    ):
												result *= n - i
												result //= i + 1
						return result
def 	__lowerCAmelCase						(		__UpperCamelCase      :			int    ):


						'''simple docstring'''






						return binomial_coefficient(2 * node_count					, __UpperCamelCase    ) // (node_count + 1)
def 	__lowerCAmelCase						(		__UpperCamelCase      :			int    ):


						'''simple docstring'''






						if n < 0:
												raise ValueError("""factorial() not defined for negative values"""    )
						snake_case_   : Optional[int]						=			1
						for i in range(1					, n + 1    ):
												result *= i
						return result
def 	__lowerCAmelCase						(		__UpperCamelCase      :			int    ):


						'''simple docstring'''






						return catalan_number(__UpperCamelCase    ) * factorial(__UpperCamelCase    )


if __name__ == "__main__":
					__lowerCAmelCase       :					Optional[Any]      					=					int(input('''Enter the number of nodes: ''').strip() or 0)
					if node_count <= 0:
										raise ValueError('''We need some nodes to work with.''')
					print(
					    F'''Given {node_count} nodes, there are {binary_tree_count(node_count)} '''
					    F'''binary trees and {catalan_number(node_count)} binary search trees.'''
					)

