





'''simple docstring'''

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

    A__				=			[0] * (upper_limit + 1)

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

from __future__ import annotations






class    UpperCAmelCase	:
 def __init__(				self      :Optional[int]						,       lowercase_      :int							)->							None:
     A__				=			order

     # a_{0} ... a_{k}
     A__				=			[1.0] + [0.0] * order
     # b_{0} ... b_{k}
     A__				=			[1.0] + [0.0] * order

     # x[n-1] ... x[n-k]
     A__				=			[0.0] * self.order
     # y[n-1] ... y[n-k]
     A__				=			[0.0] * self.order
 def      UpperCAmelCase_							(				self      :List[str]						,       lowercase_      :list[float]						,       lowercase_      :list[float]							)->							None:
     if len(lowercase_							) < self.order:
         A__				=			[1.0, *a_coeffs]

     if len(lowercase_							) != self.order + 1:
         A__				=			(
             F"Expected a_coeffs to have {self.order + 1} elements "
             F"for {self.order}-order filter, got {len(lowercase_							)}"
         )
         raise ValueError(lowercase_							)

     if len(lowercase_							) != self.order + 1:
         A__				=			(
             F"Expected b_coeffs to have {self.order + 1} elements "
             F"for {self.order}-order filter, got {len(lowercase_							)}"
         )
         raise ValueError(lowercase_							)

     A__				=			a_coeffs
     A__				=			b_coeffs



 def      UpperCAmelCase_							(				self      :Optional[int]						,       lowercase_      :float							)->							float:
     A__				=			0.0

     # Start at index 1 and do index 0 at the end.
     for i in range(1						,       self.order + 1							):
         result += (
             self.b_coeffs[i] * self.input_history[i - 1]
             - self.a_coeffs[i] * self.output_history[i - 1]
         )

     A__				=			(result + self.b_coeffs[0] * sample) / self.a_coeffs[0]

     A__				=			self.input_history[:-1]
     A__				=			self.output_history[:-1]

     A__				=			sample
     A__				=			result

     return result



