




import string

# frequency taken from https://en.wikipedia.org/wiki/Letter_frequency
SCREAMING_SNAKE_CASE__       :      Union[str, Any]  =   {
    '''E''': 12.70,
    '''T''': 9.06,
    '''A''': 8.17,
    '''O''': 7.51,
    '''I''': 6.97,
    '''N''': 6.75,
    '''S''': 6.33,
    '''H''': 6.09,
    '''R''': 5.99,
    '''D''': 4.25,
    '''L''': 4.03,
    '''C''': 2.78,
    '''U''': 2.76,
    '''M''': 2.41,
    '''W''': 2.36,
    '''F''': 2.23,
    '''G''': 2.02,
    '''Y''': 1.97,
    '''P''': 1.93,
    '''B''': 1.29,
    '''V''': 0.98,
    '''K''': 0.77,
    '''J''': 0.15,
    '''X''': 0.15,
    '''Q''': 0.10,
    '''Z''': 0.07,
}
SCREAMING_SNAKE_CASE__       :      Optional[Any]  =   '''ETAOINSHRDLCUMWFGYPBVKJXQZ'''
SCREAMING_SNAKE_CASE__       :      Dict  =   '''ABCDEFGHIJKLMNOPQRSTUVWXYZ'''

def      A      (      _SCREAMING_SNAKE_CASE    )	-> int:
       lowerCamelCase   :      Optional[int]			 =					{letter: 0 for letter in string.ascii_uppercase}
       for letter in message.upper():
              if letter in LETTERS:
                     letter_count[letter] += 1

       return letter_count

def      A      (      _SCREAMING_SNAKE_CASE    )	-> Union[str, Any]:
       return x[0]

def      A      (      _SCREAMING_SNAKE_CASE    )	-> Optional[Any]:
       lowerCamelCase   :      Optional[int]			 =					get_letter_count(lowerCAmelCase_    )
       lowerCamelCase   :      List[Any]			 =					{
           freq: [] for letter, freq in letter_to_freq.items()
       }
       for letter in LETTERS:
              freq_to_letter[letter_to_freq[letter]].append(lowerCAmelCase_    )

       lowerCamelCase   :      Tuple			 =					{}

       for freq in freq_to_letter:
              freq_to_letter[freq].sort(key=ETAOIN.find ,reverse=lowerCAmelCase_    )
              lowerCamelCase   :      Dict			 =					"".join(freq_to_letter[freq]    )

       lowerCamelCase   :      List[str]			 =					list(freq_to_letter_str.items()    )
       freq_pairs.sort(key=lowerCAmelCase_ ,reverse=lowerCAmelCase_    )

       lowerCamelCase   :      Union[str, Any]			 =					[freq_pair[1] for freq_pair in freq_pairs]

       return "".join(lowerCAmelCase_    )

def      A      (      _SCREAMING_SNAKE_CASE    )	-> Dict:
       lowerCamelCase   :      int			 =					get_frequency_order(lowerCAmelCase_    )
       lowerCamelCase   :      List[str]			 =					0
       for common_letter in ETAOIN[:6]:
              if common_letter in freq_order[:6]:
                     match_score += 1

       for uncommon_letter in ETAOIN[-6:]:
              if uncommon_letter in freq_order[-6:]:
                     match_score += 1

       return match_score


if __name__ == "__main__":
       import doctest

       doctest.testmod()










"""simple docstring"""







def    UpperCAmelCase__       (lowerCAmelCase_   ):




					'''simple docstring'''


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

					__SCREAMING_SNAKE_CASE						   =				[0] * (upper_limit + 1)

					# Base case: C(0) = C(1) = 1
					__SCREAMING_SNAKE_CASE						   =				1
					if upper_limit > 0:
										__SCREAMING_SNAKE_CASE						   =				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__				:							List[str]						=     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()
