





def 				SCREAMING_SNAKE_CASE__							(	snake_case__	:int  )   ->    "list[int]":
  if upper_limit < 0:
    raise ValueError('Limit for the Catalan sequence must be ≥ 0'  )

  _lowercase						    =			[0] * (upper_limit + 1)

  # Base case: C(0) = C(1) = 1
  _lowercase						    =			1
  if upper_limit > 0:
    _lowercase						    =			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(snake_case__  ):
      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:
                  snake_case								=							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"""




import unittest

from transformers import AutoTokenizer, FalconConfig, is_torch_available
from transformers.testing_utils import require_torch, slow, torch_device

from ...generation.test_utils import GenerationTesterMixin
from ...test_configuration_common import ConfigTester
from ...test_modeling_common import ModelTesterMixin, ids_tensor, random_attention_mask
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
					import torch

					from transformers import (
					    FalconForCausalLM,
					    FalconForQuestionAnswering,
					    FalconForSequenceClassification,
					    FalconForTokenClassification,
					    FalconModel,
					)






class        __magic_name__				:






				'''simple docstring'''





				def __init__(			self						,					_a						,					_a=3						,					_a=7						,					_a=True						,					_a=True						,					_a=False						,					_a=True						,					_a=99						,					_a=32						,					_a=5						,					_a=4						,					_a=37						,					_a="gelu"						,					_a=0.1						,					_a=0.1						,					_a=512						,					_a=16						,					_a=2						,					_a=0.02						,					_a=3						,					_a=4						,					_a=None						,					):





							"""simple docstring"""
							lowerCamelCase      =   parent
							lowerCamelCase      =   batch_size
							lowerCamelCase      =   seq_length
							lowerCamelCase      =   is_training
							lowerCamelCase      =   use_input_mask
							lowerCamelCase      =   use_token_type_ids
							lowerCamelCase      =   use_labels
							lowerCamelCase      =   vocab_size
							lowerCamelCase      =   hidden_size
							lowerCamelCase      =   num_hidden_layers
							lowerCamelCase      =   num_attention_heads
							lowerCamelCase      =   intermediate_size
							lowerCamelCase      =   hidden_act
							lowerCamelCase      =   hidden_dropout_prob
							lowerCamelCase      =   attention_probs_dropout_prob
							lowerCamelCase      =   max_position_embeddings
							lowerCamelCase      =   type_vocab_size
							lowerCamelCase      =   type_sequence_label_size
							lowerCamelCase      =   initializer_range
							lowerCamelCase      =   num_labels
							lowerCamelCase      =   num_choices
							lowerCamelCase      =   scope





				def   _lowerCAmelCase							(			self					):





							"""simple docstring"""
							lowerCamelCase      =   ids_tensor([self.batch_size, self.seq_length]						,					self.vocab_size					)

							lowerCamelCase      =   None
							if self.use_input_mask:
										lowerCamelCase      =   random_attention_mask([self.batch_size, self.seq_length]					)

							lowerCamelCase      =   None

							lowerCamelCase      =   None
							lowerCamelCase      =   None
							lowerCamelCase      =   None
							if self.use_labels:
										lowerCamelCase      =   ids_tensor([self.batch_size]						,					self.type_sequence_label_size					)
										lowerCamelCase      =   ids_tensor([self.batch_size, self.seq_length]						,					self.num_labels					)
										lowerCamelCase      =   ids_tensor([self.batch_size]						,					self.num_choices					)

							lowerCamelCase      =   self.get_config()

							return config, input_ids, token_type_ids, input_mask, sequence_labels, token_labels, choice_labels





				def   _lowerCAmelCase							(			self					):





							"""simple docstring"""
							return FalconConfig(
							    vocab_size=self.vocab_size						,					hidden_size=self.hidden_size						,					num_hidden_layers=self.num_hidden_layers						,					num_attention_heads=self.num_attention_heads						,					intermediate_size=self.intermediate_size						,					hidden_act=self.hidden_act						,					hidden_dropout_prob=self.hidden_dropout_prob						,					attention_probs_dropout_prob=self.attention_probs_dropout_prob						,					max_position_embeddings=self.max_position_embeddings						,					type_vocab_size=self.type_vocab_size						,					is_decoder=_a						,					initializer_range=self.initializer_range						,					pad_token_id=1						,					new_decoder_architecture=_a						,					)





				def   _lowerCAmelCase							(			self						,					_a						,					_a						,					_a						,					_a						,					_a						,					_a						,					_a					):





							"""simple docstring"""
							lowerCamelCase      =   FalconModel(config=_a					)
							model.to(_a					)
							model.eval()
							lowerCamelCase      =   model(_a						,					attention_mask=_a					)
							lowerCamelCase      =   model(_a					)
							self.parent.assertEqual(result.last_hidden_state.shape						,					(self.batch_size, self.seq_length, self.hidden_size)					)





				def   _lowerCAmelCase							(			self						,					_a						,					_a						,					_a						,					_a						,					_a						,					_a						,					_a						,					_a						,					_a						,					):





							"""simple docstring"""
							lowerCamelCase      =   True
							lowerCamelCase      =   FalconModel(_a					)
							model.to(_a					)
							model.eval()
							lowerCamelCase      =   model(
							    _a						,					attention_mask=_a						,					encoder_hidden_states=_a						,					encoder_attention_mask=_a						,					)
							lowerCamelCase      =   model(
							    _a						,					attention_mask=_a						,					encoder_hidden_states=_a						,					)
							lowerCamelCase      =   model(_a						,					attention_mask=_a					)
							self.parent.assertEqual(result.last_hidden_state.shape						,					(self.batch_size, self.seq_length, self.hidden_size)					)





				def   _lowerCAmelCase							(			self						,					_a						,					_a						,					_a						,					_a						,					_a						,					_a						,					_a						,					_a						,					_a						,					):





							"""simple docstring"""
							lowerCamelCase      =   FalconForCausalLM(config=_a					)
							model.to(_a					)
							model.eval()
							lowerCamelCase      =   model(_a						,					attention_mask=_a						,					labels=_a					)
							self.parent.assertEqual(result.logits.shape						,					(self.batch_size, self.seq_length, self.vocab_size)					)





				def   _lowerCAmelCase							(			self						,					_a						,					_a						,					_a						,					_a						,					_a						,					_a						,					_a						,					_a						,					_a						,					):





							"""simple docstring"""
							lowerCamelCase      =   True
							lowerCamelCase      =   True
							lowerCamelCase      =   FalconForCausalLM(config=_a					)
							model.to(_a					)
							model.eval()

							# first forward pass
							lowerCamelCase      =   model(
							    _a						,					attention_mask=_a						,					encoder_hidden_states=_a						,					encoder_attention_mask=_a						,					use_cache=_a						,					)
							lowerCamelCase      =   outputs.past_key_values

							# create hypothetical multiple next token and extent to next_input_ids
							lowerCamelCase      =   ids_tensor((self.batch_size, 3)						,					config.vocab_size					)
							lowerCamelCase      =   ids_tensor((self.batch_size, 3)						,					vocab_size=2					)

							# append to next input_ids and
							lowerCamelCase      =   torch.cat([input_ids, next_tokens]						,					dim=-1					)
							lowerCamelCase      =   torch.cat([input_mask, next_mask]						,					dim=-1					)

							lowerCamelCase      =   model(
							    _a						,					attention_mask=_a						,					encoder_hidden_states=_a						,					encoder_attention_mask=_a						,					output_hidden_states=_a						,					)["""hidden_states"""][0]
							lowerCamelCase      =   model(
							    _a						,					attention_mask=_a						,					encoder_hidden_states=_a						,					encoder_attention_mask=_a						,					past_key_values=_a						,					output_hidden_states=_a						,					)["""hidden_states"""][0]

							# select random slice
							lowerCamelCase      =   ids_tensor((1,)						,					output_from_past.shape[-1]					).item()
							lowerCamelCase      =   output_from_no_past[:, -3:, random_slice_idx].detach()
							lowerCamelCase      =   output_from_past[:, :, random_slice_idx].detach()

							self.parent.assertTrue(output_from_past_slice.shape[1] == next_tokens.shape[1]					)

							# test that outputs are equal for slice
							self.parent.assertTrue(torch.allclose(_a						,					_a						,					atol=1e-3					)					)





				def   _lowerCAmelCase							(			self					):





							"""simple docstring"""
							lowerCamelCase      =   self.prepare_config_and_inputs()
							(
							    (
							    lowerCamelCase
							) ,  (
							    lowerCamelCase
							) ,  (
							    lowerCamelCase
							) ,  (
							    lowerCamelCase
							) ,  (
							    lowerCamelCase
							) ,  (
							    lowerCamelCase
							) ,  (
							    lowerCamelCase
							) ,  
							)      =   config_and_inputs
							lowerCamelCase      =   {"""input_ids""": input_ids, """attention_mask""": input_mask}
							return config, inputs_dict






@require_torch
class        __magic_name__				(			UpperCAmelCase__		,   UpperCAmelCase__		,   UpperCAmelCase__		,   unittest.TestCase							):






				'''simple docstring'''
				__UpperCamelCase         =		(
				    (
				        FalconModel,
				        FalconForCausalLM,
				        FalconForSequenceClassification,
				        FalconForTokenClassification,
				        FalconForQuestionAnswering,
				    )
				    if is_torch_available()
				    else ()
				)
				__UpperCamelCase         =		(FalconForCausalLM,) if is_torch_available() else ()
				__UpperCamelCase         =		(
				    {
				        "feature-extraction": FalconModel,
				        "text-classification": FalconForSequenceClassification,
				        "text-generation": FalconForCausalLM,
				        "question-answering": FalconForQuestionAnswering,
				        "token-classification": FalconForTokenClassification,
				        "zero-shot": FalconForSequenceClassification,
				    }
				    if is_torch_available()
				    else {}
				)
				__UpperCamelCase         =		False
				__UpperCamelCase         =		False





				def   _lowerCAmelCase							(			self					):





							"""simple docstring"""
							lowerCamelCase      =   FalconModelTester(self					)
							lowerCamelCase      =   ConfigTester(self						,					config_class=_a						,					hidden_size=37					)





				def   _lowerCAmelCase							(			self					):





							"""simple docstring"""
							self.config_tester.run_common_tests()





				def   _lowerCAmelCase							(			self					):





							"""simple docstring"""
							lowerCamelCase      =   self.model_tester.prepare_config_and_inputs()
							self.model_tester.create_and_check_model(*_a					)





				def   _lowerCAmelCase							(			self					):





							"""simple docstring"""
							lowerCamelCase ,  *lowerCamelCase      =   self.model_tester.prepare_config_and_inputs()
							for alibi in [True, False]:
										lowerCamelCase      =   alibi
										self.model_tester.create_and_check_model(_a						,					*_a					)





				def   _lowerCAmelCase							(			self					):





							"""simple docstring"""
							lowerCamelCase ,  lowerCamelCase      =   self.model_tester.prepare_config_and_inputs_for_common()
							lowerCamelCase      =   3
							lowerCamelCase      =   input_dict["""input_ids"""]
							lowerCamelCase      =   input_ids.ne(1					).to(_a					)
							lowerCamelCase      =   ids_tensor([self.model_tester.batch_size]						,					self.model_tester.type_sequence_label_size					)
							lowerCamelCase      =   FalconForSequenceClassification(_a					)
							model.to(_a					)
							model.eval()
							lowerCamelCase      =   model(_a						,					attention_mask=_a						,					labels=_a					)
							self.assertEqual(result.logits.shape						,					(self.model_tester.batch_size, self.model_tester.num_labels)					)





				def   _lowerCAmelCase							(			self					):





							"""simple docstring"""
							lowerCamelCase ,  lowerCamelCase      =   self.model_tester.prepare_config_and_inputs_for_common()
							lowerCamelCase      =   3
							lowerCamelCase      =   """single_label_classification"""
							lowerCamelCase      =   input_dict["""input_ids"""]
							lowerCamelCase      =   input_ids.ne(1					).to(_a					)
							lowerCamelCase      =   ids_tensor([self.model_tester.batch_size]						,					self.model_tester.type_sequence_label_size					)
							lowerCamelCase      =   FalconForSequenceClassification(_a					)
							model.to(_a					)
							model.eval()
							lowerCamelCase      =   model(_a						,					attention_mask=_a						,					labels=_a					)
							self.assertEqual(result.logits.shape						,					(self.model_tester.batch_size, self.model_tester.num_labels)					)





				def   _lowerCAmelCase							(			self					):





							"""simple docstring"""
							lowerCamelCase ,  lowerCamelCase      =   self.model_tester.prepare_config_and_inputs_for_common()
							lowerCamelCase      =   input_dict["""input_ids"""]
							lowerCamelCase      =   FalconForCausalLM(_a					)
							model.to(_a					)
							model.eval()
							lowerCamelCase      =   model(_a						,					use_cache=_a					)
							lowerCamelCase      =   input_ids.shape[0]
							lowerCamelCase      =   model._convert_to_rw_cache(result.past_key_values					)
							lowerCamelCase      =   model._convert_cache_to_standard_format(_a						,					_a					)
							for layer in range(len(_a					)					):
										for tensor_idx in range(2					):
													self.assertTrue(rw_cache[layer][tensor_idx].ndim == 3					)
													self.assertTrue(result.past_key_values[layer][tensor_idx].ndim == 4					)
													self.assertTrue(
													    torch.all(result.past_key_values[layer][tensor_idx] == standard_cache[layer][tensor_idx]					)					)





				def   _lowerCAmelCase							(			self					):





							"""simple docstring"""
							lowerCamelCase ,  lowerCamelCase      =   self.model_tester.prepare_config_and_inputs_for_common()
							lowerCamelCase      =   3
							lowerCamelCase      =   """multi_label_classification"""
							lowerCamelCase      =   input_dict["""input_ids"""]
							lowerCamelCase      =   input_ids.ne(1					).to(_a					)
							lowerCamelCase      =   ids_tensor(
							    [self.model_tester.batch_size, config.num_labels]						,					self.model_tester.type_sequence_label_size					).to(torch.float					)
							lowerCamelCase      =   FalconForSequenceClassification(_a					)
							model.to(_a					)
							model.eval()
							lowerCamelCase      =   model(_a						,					attention_mask=_a						,					labels=_a					)
							self.assertEqual(result.logits.shape						,					(self.model_tester.batch_size, self.model_tester.num_labels)					)





				def   _lowerCAmelCase							(			self					):





							"""simple docstring"""
							# Falcon can have different numbers of KV-heads than the number of query heads, so we need
							# to override this test to use the right head counts.
							for model_class in self.all_generative_model_classes:
										lowerCamelCase ,  lowerCamelCase      =   self.model_tester.prepare_config_and_inputs_for_common()

										# If it doesn't support cache, pass the test
										if not hasattr(_a						,					"""use_cache"""					):
													return

										lowerCamelCase      =   model_class(_a					).to(_a					)
										if "use_cache" not in inputs:
													lowerCamelCase      =   True
										lowerCamelCase      =   model(**_a					)

										# If "past_key_values" is not returned, pass the test (e.g. RWKV uses a different cache name and format)
										if "past_key_values" not in outputs:
													return

										lowerCamelCase      =   (
										    getattr(_a						,					"""decoder_layers"""						,					_a					)
										    or getattr(_a						,					"""num_decoder_layers"""						,					_a					)
										    or config.num_hidden_layers
										)
										lowerCamelCase      =   getattr(_a						,					"""num_kv_heads"""						,					config.num_attention_heads					)
										lowerCamelCase      =   getattr(_a						,					"""d_model"""						,					config.hidden_size					)
										lowerCamelCase      =   embed_dim // num_attention_heads

										lowerCamelCase      =   outputs["""past_key_values"""]
										self.assertEqual(len(_a					)						,					_a					)

										lowerCamelCase ,  lowerCamelCase      =   inputs["""input_ids"""].shape
										for i in range(_a					):
													if config.new_decoder_architecture:
																lowerCamelCase      =   config.num_attention_heads
													elif config.multi_query:
																lowerCamelCase      =   1
													self.assertEqual(len(past_kv[0]					)						,					2					)  # K V for the decoder = 2
													self.assertEqual(
													    past_kv[i][0].shape						,					(batch_size, num_attention_heads, seq_length, per_head_embed_dim)					)
													self.assertEqual(
													    past_kv[i][1].shape						,					(batch_size, num_attention_heads, seq_length, per_head_embed_dim)					)






@require_torch
class        __magic_name__				(			unittest.TestCase							):






				'''simple docstring'''





				@slow
				def   _lowerCAmelCase							(			self					):





							"""simple docstring"""
							lowerCamelCase      =   AutoTokenizer.from_pretrained("""Rocketknight1/falcon-rw-1b"""					)
							lowerCamelCase      =   FalconForCausalLM.from_pretrained("""Rocketknight1/falcon-rw-1b"""					)
							model.eval()
							model.to(_a					)
							lowerCamelCase      =   tokenizer("""My favorite food is"""						,					return_tensors="""pt"""					).to(_a					)

							lowerCamelCase      =   (
							    """My favorite food is pizza. I love it so much that I have a pizza party every year for my birthday."""
							)

							lowerCamelCase      =   model.generate(**_a						,					do_sample=_a						,					max_new_tokens=19					)
							lowerCamelCase      =   tokenizer.batch_decode(_a					)[0]

							self.assertEqual(_a						,					_a					)





				@slow
				def   _lowerCAmelCase							(			self					):





							"""simple docstring"""
							# The big models are way too big for the CI, so we use tiny random models that resemble their
							# architectures but with much smaller and fewer layers
							for repo in ["Rocketknight1/tiny-random-falcon-7b", "Rocketknight1/tiny-random-falcon-40b"]:
										lowerCamelCase      =   AutoTokenizer.from_pretrained(_a					)
										lowerCamelCase      =   FalconForCausalLM.from_pretrained(_a					)
										model.eval()
										model.to(_a					)
										lowerCamelCase      =   tokenizer("""My favorite food is"""						,					return_tensors="""pt"""					).to(_a					)

										# We just test that these run without errors - the models are randomly initialized
										# and so the actual text outputs will be garbage
										model.generate(**_a						,					do_sample=_a						,					max_new_tokens=4					)
										model.generate(**_a						,					do_sample=_a						,					max_new_tokens=4					)
										model.generate(**_a						,					num_beams=2						,					max_new_tokens=4					)





				@slow
				def   _lowerCAmelCase							(			self					):





							"""simple docstring"""
							# The big models are way too big for the CI, so we use tiny random models that resemble their
							# architectures but with much smaller and fewer layers
							with torch.no_grad():
										for repo in [
										    "Rocketknight1/falcon-rw-1b",
										    "Rocketknight1/tiny-random-falcon-7b",
										    "Rocketknight1/tiny-random-falcon-40b",
										]:
													lowerCamelCase      =   AutoTokenizer.from_pretrained(_a					)
													lowerCamelCase      =   FalconForCausalLM.from_pretrained(_a					)
													model.eval()
													model.to(device=_a					)
													lowerCamelCase      =   tokenizer("""My favorite food is"""						,					return_tensors="""pt"""					).to(_a					)

													# Test results are the same with and without cache
													lowerCamelCase      =   model.generate(**_a						,					do_sample=_a						,					max_new_tokens=20						,					use_cache=_a					)
													lowerCamelCase      =   model.generate(**_a						,					do_sample=_a						,					max_new_tokens=20						,					use_cache=_a					)
													self.assertTrue((outputs_cache - outputs_no_cache).sum().item() == 0					)



