


"""simple docstring"""
import unittest
from unittest.util import safe_repr

from transformers import AutoTokenizer, RwkvConfig, 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, floats_tensor, ids_tensor, random_attention_mask
from ...test_pipeline_mixin import PipelineTesterMixin


if is_torch_available():
 import torch

 from transformers import (
     RWKV_PRETRAINED_MODEL_ARCHIVE_LIST,
     RwkvForCausalLM,
     RwkvModel,
 )
 from transformers.pytorch_utils import is_torch_greater_or_equal_than_2_0
else:
 UpperCAmelCase   =	False




class   lowercase__							:





   def __init__(       self			,      SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE=14			,      SCREAMING_SNAKE_CASE=7			,      SCREAMING_SNAKE_CASE=True			,      SCREAMING_SNAKE_CASE=False			,      SCREAMING_SNAKE_CASE=True			,      SCREAMING_SNAKE_CASE=True			,      SCREAMING_SNAKE_CASE=True			,      SCREAMING_SNAKE_CASE=99			,      SCREAMING_SNAKE_CASE=32			,      SCREAMING_SNAKE_CASE=5			,      SCREAMING_SNAKE_CASE=37			,      SCREAMING_SNAKE_CASE="gelu"			,      SCREAMING_SNAKE_CASE=0.1			,      SCREAMING_SNAKE_CASE=0.1			,      SCREAMING_SNAKE_CASE=512			,      SCREAMING_SNAKE_CASE=16			,      SCREAMING_SNAKE_CASE=2			,      SCREAMING_SNAKE_CASE=3			,      SCREAMING_SNAKE_CASE=4			,      SCREAMING_SNAKE_CASE=None			,      )     ->     str:
      _lowerCamelCase  :				List[Any]      =		parent
      _lowerCamelCase  :				Union[str, Any]      =		batch_size
      _lowerCamelCase  :				Any      =		seq_length
      _lowerCamelCase  :				Dict      =		is_training
      _lowerCamelCase  :				int      =		use_token_type_ids
      _lowerCamelCase  :				Dict      =		use_input_mask
      _lowerCamelCase  :				Union[str, Any]      =		use_labels
      _lowerCamelCase  :				Tuple      =		use_mc_token_ids
      _lowerCamelCase  :				Any      =		vocab_size
      _lowerCamelCase  :				Optional[int]      =		hidden_size
      _lowerCamelCase  :				Optional[Any]      =		num_hidden_layers
      _lowerCamelCase  :				int      =		intermediate_size
      _lowerCamelCase  :				Optional[Any]      =		hidden_act
      _lowerCamelCase  :				str      =		hidden_dropout_prob
      _lowerCamelCase  :				Union[str, Any]      =		attention_probs_dropout_prob
      _lowerCamelCase  :				List[Any]      =		max_position_embeddings
      _lowerCamelCase  :				Any      =		type_vocab_size
      _lowerCamelCase  :				Optional[Any]      =		type_sequence_label_size
      _lowerCamelCase  :				List[str]      =		num_labels
      _lowerCamelCase  :				List[str]      =		num_choices
      _lowerCamelCase  :				Optional[int]      =		scope
      _lowerCamelCase  :				Union[str, Any]      =		vocab_size - 1
      _lowerCamelCase  :				int      =		vocab_size - 1
      _lowerCamelCase  :				List[str]      =		vocab_size - 1





   def 		UpperCamelCase_     (       self)     ->     str:
      return RwkvConfig.from_pretrained("""sgugger/rwkv-4-pile-7b""")





   def 		UpperCamelCase_     (       self			,      SCREAMING_SNAKE_CASE=False			,      SCREAMING_SNAKE_CASE=False			,      SCREAMING_SNAKE_CASE=False)     ->     Optional[int]:
      _lowerCamelCase  :				Dict      =		ids_tensor([self.batch_size, self.seq_length]			,      self.vocab_size)

      _lowerCamelCase  :				Optional[int]      =		None
      if self.use_input_mask:
         _lowerCamelCase  :				Dict      =		random_attention_mask([self.batch_size, self.seq_length])

      _lowerCamelCase  :				Any      =		None
      if self.use_token_type_ids:
         _lowerCamelCase  :				Optional[int]      =		ids_tensor([self.batch_size, self.seq_length]			,      self.type_vocab_size)

      _lowerCamelCase  :				List[str]      =		None
      if self.use_mc_token_ids:
         _lowerCamelCase  :				List[Any]      =		ids_tensor([self.batch_size, self.num_choices]			,      self.seq_length)

      _lowerCamelCase  :				Union[str, Any]      =		None
      _lowerCamelCase  :				Dict      =		None
      _lowerCamelCase  :				Any      =		None
      if self.use_labels:
         _lowerCamelCase  :				Tuple      =		ids_tensor([self.batch_size]			,      self.type_sequence_label_size)
         _lowerCamelCase  :				Dict      =		ids_tensor([self.batch_size, self.seq_length]			,      self.num_labels)
         _lowerCamelCase  :				List[str]      =		ids_tensor([self.batch_size]			,      self.num_choices)

      _lowerCamelCase  :				Dict      =		self.get_config(
          gradient_checkpointing=SCREAMING_SNAKE_CASE			,      scale_attn_by_inverse_layer_idx=SCREAMING_SNAKE_CASE			,      reorder_and_upcast_attn=SCREAMING_SNAKE_CASE			,      )

      return (
          config,
          input_ids,
          input_mask,
          None,
          token_type_ids,
          mc_token_ids,
          sequence_labels,
          token_labels,
          choice_labels,
      )





   def 		UpperCamelCase_     (       self			,      SCREAMING_SNAKE_CASE=False			,      SCREAMING_SNAKE_CASE=False			,      SCREAMING_SNAKE_CASE=False)     ->     List[Any]:
      return RwkvConfig(
          vocab_size=self.vocab_size			,      hidden_size=self.hidden_size			,      num_hidden_layers=self.num_hidden_layers			,      intermediate_size=self.intermediate_size			,      activation_function=self.hidden_act			,      resid_pdrop=self.hidden_dropout_prob			,      attn_pdrop=self.attention_probs_dropout_prob			,      n_positions=self.max_position_embeddings			,      type_vocab_size=self.type_vocab_size			,      use_cache=SCREAMING_SNAKE_CASE			,      bos_token_id=self.bos_token_id			,      eos_token_id=self.eos_token_id			,      pad_token_id=self.pad_token_id			,      gradient_checkpointing=SCREAMING_SNAKE_CASE			,      scale_attn_by_inverse_layer_idx=SCREAMING_SNAKE_CASE			,      reorder_and_upcast_attn=SCREAMING_SNAKE_CASE			,      )





   def 		UpperCamelCase_     (       self)     ->     str:
      _lowerCamelCase  :				str      =		self.get_config()
      _lowerCamelCase  :				Optional[int]      =		300
      return config





   def 		UpperCamelCase_     (       self)     ->     Optional[Any]:
      (
          (
          _lowerCamelCase
      )      ,						(
          _lowerCamelCase
      )      ,						(
          _lowerCamelCase
      )      ,						(
          _lowerCamelCase
      )      ,						(
          _lowerCamelCase
      )      ,						(
          _lowerCamelCase
      )      ,						(
          _lowerCamelCase
      )      ,						(
          _lowerCamelCase
      )      ,						(
          _lowerCamelCase
      )      ,						
      )  :				Tuple      =		self.prepare_config_and_inputs()

      _lowerCamelCase  :				List[str]      =		floats_tensor([self.batch_size, self.seq_length, self.hidden_size])
      _lowerCamelCase  :				str      =		ids_tensor([self.batch_size, self.seq_length]			,      vocab_size=2)

      return (
          config,
          input_ids,
          input_mask,
          head_mask,
          token_type_ids,
          sequence_labels,
          token_labels,
          choice_labels,
          encoder_hidden_states,
          encoder_attention_mask,
      )





   def 		UpperCamelCase_     (       self			,      SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE			,      *SCREAMING_SNAKE_CASE)     ->     int:
      _lowerCamelCase  :				Any      =		True
      _lowerCamelCase  :				Tuple      =		RwkvModel(config=SCREAMING_SNAKE_CASE)
      model.to(SCREAMING_SNAKE_CASE)
      model.eval()

      _lowerCamelCase  :				Optional[int]      =		model(SCREAMING_SNAKE_CASE)

      self.parent.assertEqual(result.last_hidden_state.shape			,      (self.batch_size, self.seq_length, self.hidden_size))
      self.parent.assertEqual(len(result.hidden_states)			,      config.num_hidden_layers + 1)





   def 		UpperCamelCase_     (       self			,      SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE			,      *SCREAMING_SNAKE_CASE)     ->     Dict:
      _lowerCamelCase  :				Any      =		RwkvForCausalLM(SCREAMING_SNAKE_CASE)
      model.to(SCREAMING_SNAKE_CASE)
      model.eval()

      _lowerCamelCase  :				List[Any]      =		model(SCREAMING_SNAKE_CASE			,      labels=SCREAMING_SNAKE_CASE)
      self.parent.assertEqual(result.loss.shape			,      ())
      self.parent.assertEqual(result.logits.shape			,      (self.batch_size, self.seq_length, self.vocab_size))





   def 		UpperCamelCase_     (       self			,      SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE			,      *SCREAMING_SNAKE_CASE)     ->     List[str]:
      _lowerCamelCase  :				Dict      =		RwkvModel(config=SCREAMING_SNAKE_CASE)
      model.to(SCREAMING_SNAKE_CASE)
      model.eval()

      _lowerCamelCase  :				Union[str, Any]      =		model(SCREAMING_SNAKE_CASE)
      _lowerCamelCase  :				List[str]      =		outputs.last_hidden_state

      _lowerCamelCase  :				Optional[Any]      =		model(input_ids[:, :2])
      _lowerCamelCase  :				Any      =		outputs.last_hidden_state

      # Using the state computed on the first inputs, we will get the same output
      _lowerCamelCase  :				Dict      =		model(input_ids[:, 2:]			,      state=outputs.state)
      _lowerCamelCase  :				Optional[Any]      =		outputs.last_hidden_state

      self.parent.assertTrue(torch.allclose(torch.cat([output_one, output_two]			,      dim=1)			,      SCREAMING_SNAKE_CASE			,      atol=1e-5))





   def 		UpperCamelCase_     (       self			,      SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE			,      *SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE=False)     ->     Any:
      _lowerCamelCase  :				Dict      =		RwkvForCausalLM(SCREAMING_SNAKE_CASE)
      model.to(SCREAMING_SNAKE_CASE)
      if gradient_checkpointing:
         model.gradient_checkpointing_enable()

      _lowerCamelCase  :				Tuple      =		model(SCREAMING_SNAKE_CASE			,      labels=SCREAMING_SNAKE_CASE)
      self.parent.assertEqual(result.loss.shape			,      ())
      self.parent.assertEqual(result.logits.shape			,      (self.batch_size, self.seq_length, self.vocab_size))
      result.loss.backward()





   def 		UpperCamelCase_     (       self)     ->     int:
      _lowerCamelCase  :				Any      =		self.prepare_config_and_inputs()

      (
          (
          _lowerCamelCase
      )      ,						(
          _lowerCamelCase
      )      ,						(
          _lowerCamelCase
      )      ,						(
          _lowerCamelCase
      )      ,						(
          _lowerCamelCase
      )      ,						(
          _lowerCamelCase
      )      ,						(
          _lowerCamelCase
      )      ,						(
          _lowerCamelCase
      )      ,						(
          _lowerCamelCase
      )      ,						
      )  :				List[str]      =		config_and_inputs

      _lowerCamelCase  :				Union[str, Any]      =		{"""input_ids""": input_ids}

      return config, inputs_dict







@unittest.skipIf(
    not is_torch_greater_or_equal_than_2_0   ,reason='''See https://github.com/huggingface/transformers/pull/24204'''							)
@require_torch
class   lowercase__							(				A_   ,A_   ,A_   ,unittest.TestCase							):
   __UpperCAmelCase       					=				(RwkvModel, RwkvForCausalLM) if is_torch_available() else ()
   __UpperCAmelCase       					=				(
       {'''feature-extraction''': RwkvModel, '''text-generation''': RwkvForCausalLM} if is_torch_available() else {}
   )
   # all_generative_model_classes = (RwkvForCausalLM,) if is_torch_available() else ()
   __UpperCAmelCase       					=				False
   __UpperCAmelCase       					=				False
   __UpperCAmelCase       					=				False
   __UpperCAmelCase       					=				False
   __UpperCAmelCase       					=				False  # Rwkv does not support head masking





   def 		UpperCamelCase_     (       self)     ->     Optional[int]:
      _lowerCamelCase  :				Any      =		RwkvModelTester(self)
      _lowerCamelCase  :				str      =		ConfigTester(
          self			,      config_class=SCREAMING_SNAKE_CASE			,      n_embd=37			,      common_properties=["""hidden_size""", """num_hidden_layers"""])





   def 		UpperCamelCase_     (       self			,      SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE=None)     ->     str:
      if isinstance(SCREAMING_SNAKE_CASE			,      torch.Tensor):
         _lowerCamelCase      ,						_lowerCamelCase  :				Union[str, Any]      =		member.max().item(), member.min().item()
      elif isinstance(SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE) or isinstance(SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE):
         _lowerCamelCase      ,						_lowerCamelCase  :				List[Any]      =		max(SCREAMING_SNAKE_CASE), min(SCREAMING_SNAKE_CASE)

      if not isinstance(SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE):
         raise TypeError("""container should be a list or tuple""")
      elif len(SCREAMING_SNAKE_CASE) != 2:
         raise ValueError("""container should have 2 elements""")

      _lowerCamelCase      ,						_lowerCamelCase  :				int      =		container

      _lowerCamelCase  :				List[Any]      =		(min_value >= expected_min) and (max_value <= expected_max)

      if not is_inside_interval:
         _lowerCamelCase  :				Any      =		"""%s not found in %s""" % (safe_repr(SCREAMING_SNAKE_CASE), safe_repr(SCREAMING_SNAKE_CASE))
         self.fail(self._formatMessage(SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE))





   def 		UpperCamelCase_     (       self)     ->     Optional[Any]:
      self.config_tester.run_common_tests()





   def 		UpperCamelCase_     (       self)     ->     Any:
      _lowerCamelCase  :				Union[str, Any]      =		self.model_tester.prepare_config_and_inputs()
      self.model_tester.create_and_check_rwkv_model(*SCREAMING_SNAKE_CASE)





   def 		UpperCamelCase_     (       self)     ->     Dict:
      _lowerCamelCase  :				Dict      =		self.model_tester.prepare_config_and_inputs()
      self.model_tester.create_and_check_causl_lm(*SCREAMING_SNAKE_CASE)





   def 		UpperCamelCase_     (       self)     ->     List[str]:
      _lowerCamelCase  :				Optional[Any]      =		self.model_tester.prepare_config_and_inputs()
      self.model_tester.create_and_check_state_equivalency(*SCREAMING_SNAKE_CASE)





   def 		UpperCamelCase_     (       self)     ->     int:
      _lowerCamelCase      ,						_lowerCamelCase  :				int      =		self.model_tester.prepare_config_and_inputs_for_common()

      for model_class in self.all_model_classes:
         _lowerCamelCase  :				Tuple      =		model_class(config=SCREAMING_SNAKE_CASE)
         for name, param in model.named_parameters():
            if "time_decay" in name:
               if param.requires_grad:
                  self.assertTrue(param.data.max().item() == 3.0)
                  self.assertTrue(param.data.min().item() == -5.0)
            elif "time_first" in name:
               if param.requires_grad:
                  # check if it's a ones like
                  self.assertTrue(torch.allclose(param.data			,      torch.ones_like(param.data)			,      atol=1e-5			,      rtol=1e-5))
            elif any(x in name for x in ["""time_mix_key""", """time_mix_receptance"""]):
               if param.requires_grad:
                  self.assertInterval(
                      param.data			,      [0.0, 1.0]			,      msg=F'Parameter {name} of model {model_class} seems not properly initialized'			,      )
            elif "time_mix_value" in name:
               if param.requires_grad:
                  self.assertInterval(
                      param.data			,      [0.0, 1.3]			,      msg=F'Parameter {name} of model {model_class} seems not properly initialized'			,      )





   def 		UpperCamelCase_     (       self)     ->     str:
      _lowerCamelCase      ,						_lowerCamelCase  :				Optional[int]      =		self.model_tester.prepare_config_and_inputs_for_common()
      _lowerCamelCase  :				Union[str, Any]      =		True

      _lowerCamelCase  :				Optional[Any]      =		getattr(self.model_tester			,      """seq_length"""			,      SCREAMING_SNAKE_CASE)

      for model_class in self.all_model_classes:
         _lowerCamelCase  :				Dict      =		True
         _lowerCamelCase  :				Optional[Any]      =		False
         _lowerCamelCase  :				Union[str, Any]      =		True
         _lowerCamelCase  :				str      =		model_class(SCREAMING_SNAKE_CASE)
         model.to(SCREAMING_SNAKE_CASE)
         model.eval()

         _lowerCamelCase  :				int      =		self._prepare_for_class(SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE)
         _lowerCamelCase  :				Tuple      =		inputs["""input_ids"""].shape[0]
         with torch.no_grad():
            _lowerCamelCase  :				Tuple      =		model(**SCREAMING_SNAKE_CASE)
         _lowerCamelCase  :				Optional[int]      =		outputs.attentions
         self.assertEqual(len(SCREAMING_SNAKE_CASE)			,      self.model_tester.num_hidden_layers)

         # check that output_attentions also work using config
         del inputs_dict["output_attentions"]
         _lowerCamelCase  :				str      =		True
         _lowerCamelCase  :				Any      =		model_class(SCREAMING_SNAKE_CASE)
         model.to(SCREAMING_SNAKE_CASE)
         model.eval()

         _lowerCamelCase  :				Optional[int]      =		self._prepare_for_class(SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE)
         _lowerCamelCase  :				Union[str, Any]      =		inputs["""input_ids"""].shape[0]
         with torch.no_grad():
            _lowerCamelCase  :				Any      =		model(**SCREAMING_SNAKE_CASE)
         _lowerCamelCase  :				Union[str, Any]      =		outputs.attentions
         self.assertEqual(len(SCREAMING_SNAKE_CASE)			,      self.model_tester.num_hidden_layers)

         self.assertListEqual(
             list(attentions[0].shape[-3:])			,      [batch_size, seq_len, config.hidden_size]			,      )
         _lowerCamelCase  :				Optional[Any]      =		len(SCREAMING_SNAKE_CASE)

         # Check attention is always last and order is fine
         _lowerCamelCase  :				Union[str, Any]      =		True
         _lowerCamelCase  :				List[str]      =		True
         _lowerCamelCase  :				Union[str, Any]      =		model_class(SCREAMING_SNAKE_CASE)
         model.to(SCREAMING_SNAKE_CASE)
         model.eval()

         _lowerCamelCase  :				Dict      =		self._prepare_for_class(SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE)
         _lowerCamelCase  :				Any      =		inputs["""input_ids"""].shape[0]
         with torch.no_grad():
            _lowerCamelCase  :				str      =		model(**SCREAMING_SNAKE_CASE)

         _lowerCamelCase  :				Tuple      =		1
         self.assertEqual(out_len + added_hidden_states			,      len(SCREAMING_SNAKE_CASE))

         _lowerCamelCase  :				Any      =		outputs.attentions

         self.assertEqual(len(SCREAMING_SNAKE_CASE)			,      self.model_tester.num_hidden_layers)
         self.assertListEqual(
             list(self_attentions[0].shape[-3:])			,      [batch_size, seq_len, config.hidden_size]			,      )





   @slow
   def 		UpperCamelCase_     (       self)     ->     Any:
      for model_name in RWKV_PRETRAINED_MODEL_ARCHIVE_LIST[:1]:
         _lowerCamelCase  :				Union[str, Any]      =		RwkvModel.from_pretrained(SCREAMING_SNAKE_CASE)
         self.assertIsNotNone(SCREAMING_SNAKE_CASE)







@unittest.skipIf(
    not is_torch_greater_or_equal_than_2_0   ,reason='''See https://github.com/huggingface/transformers/pull/24204'''							)
@slow
class   lowercase__							(				unittest.TestCase							):





   def 		UpperCamelCase_     (       self)     ->     str:
      _lowerCamelCase  :				int      =		"""RWKV/rwkv-4-169m-pile"""
      _lowerCamelCase  :				Optional[Any]      =		AutoTokenizer.from_pretrained(self.model_id)





   def 		UpperCamelCase_     (       self)     ->     List[Any]:
      _lowerCamelCase  :				List[str]      =		"""Hello my name is Jasmine and I am a newbie to the"""
      _lowerCamelCase  :				str      =		RwkvForCausalLM.from_pretrained(self.model_id).to(SCREAMING_SNAKE_CASE)

      _lowerCamelCase  :				Optional[int]      =		self.tokenizer("""Hello my name is"""			,      return_tensors="""pt""").input_ids.to(SCREAMING_SNAKE_CASE)
      _lowerCamelCase  :				int      =		model.generate(SCREAMING_SNAKE_CASE			,      max_new_tokens=10)
      _lowerCamelCase  :				List[Any]      =		self.tokenizer.decode(output[0].tolist())

      self.assertEqual(SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE)





   def 		UpperCamelCase_     (       self)     ->     int:
      _lowerCamelCase  :				Tuple      =		"""Hello my name is Jasmine and I am a newbie to the"""

      _lowerCamelCase  :				Optional[Any]      =		self.tokenizer("""Hello my name is"""			,      return_tensors="""pt""").input_ids.to(SCREAMING_SNAKE_CASE)
      _lowerCamelCase  :				Union[str, Any]      =		RwkvForCausalLM.from_pretrained(self.model_id			,      torch_dtype=torch.bfloataa).to(SCREAMING_SNAKE_CASE)

      _lowerCamelCase  :				str      =		model.generate(SCREAMING_SNAKE_CASE			,      max_new_tokens=10)
      _lowerCamelCase  :				Optional[int]      =		self.tokenizer.decode(output[0].tolist())

      self.assertEqual(SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE)





"""simple docstring"""
import timeit




class   lowercase__							:





   def __init__(       self			,      SCREAMING_SNAKE_CASE)     ->     Tuple:
      if isinstance(SCREAMING_SNAKE_CASE			,      SCREAMING_SNAKE_CASE):  # Initializes a matrix identical to the one provided.
         _lowerCamelCase  :				List[str]      =		arg
         _lowerCamelCase  :				List[str]      =		len(SCREAMING_SNAKE_CASE)
      else:  # Initializes a square matrix of the given size and set values to zero.
         _lowerCamelCase  :				List[Any]      =		arg
         _lowerCamelCase  :				Union[str, Any]      =		[[0 for _ in range(self.n)] for _ in range(self.n)]





   def __mul__(       self			,      SCREAMING_SNAKE_CASE)     ->     Optional[Any]:
      _lowerCamelCase  :				List[Any]      =		Matrix(self.n)
      for i in range(self.n):
         for j in range(self.n):
            for k in range(self.n):
               matrix.t[i][j] += self.t[i][k] * b.t[k][j]
      return matrix







def 							_snake_case			(      __snake_case       :			Union[str, Any]	,   __snake_case       :			List[Any]      ):




   """simple docstring"""







   _lowerCamelCase  :				List[Any]      =		Matrix([[1, 0], [0, 1]]      )
   while b > 0:
      if b & 1:
         matrix *= a
      a *= a
      b >>= 1
   return matrix

def 							_snake_case			(      __snake_case       :			List[str]	,   __snake_case       :			str	,   __snake_case       :			List[Any]      ):




   """simple docstring"""







   if n == 1:
      return fa
   elif n == 2:
      return fa
   _lowerCamelCase  :				Any      =		Matrix([[1, 1], [1, 0]]      )
   _lowerCamelCase  :				List[str]      =		modular_exponentiation(__snake_case	,   n - 2      )
   return fa * matrix.t[0][0] + fa * matrix.t[0][1]

def 							_snake_case			(      __snake_case       :			int	,   __snake_case       :			Optional[int]	,   __snake_case       :			List[Any]      ):




   """simple docstring"""







   if n == 1:
      return fa
   elif n == 2:
      return fa

   _lowerCamelCase  :				Optional[Any]      =		fa
   _lowerCamelCase  :				int      =		fa
   n -= 2

   while n > 0:
      _lowerCamelCase      ,						_lowerCamelCase  :				Tuple      =		fn_a + fn_a, fn_a
      n -= 1

   return fn_a

def 							_snake_case			(      ):




   """simple docstring"""







   _lowerCamelCase  :				List[str]      =		"""
from random import randint
from __main__ import fibonacci_with_matrix_exponentiation
"""
   _lowerCamelCase  :				int      =		"""fibonacci_with_matrix_exponentiation(randint(1,70000), 1, 1)"""
   _lowerCamelCase  :				Tuple      =		timeit.timeit(setup=__snake_case	,   stmt=__snake_case	,   number=100      )
   print("""With matrix exponentiation the average execution time is """	,   exec_time / 100      )
   return exec_time

def 							_snake_case			(      ):




   """simple docstring"""







   _lowerCamelCase  :				Dict      =		"""
from random import randint
from __main__ import simple_fibonacci
"""
   _lowerCamelCase  :				Optional[int]      =		"""simple_fibonacci(randint(1,70000), 1, 1)"""
   _lowerCamelCase  :				List[Any]      =		timeit.timeit(setup=__snake_case	,   stmt=__snake_case	,   number=100      )
   print(
       """Without matrix exponentiation the average execution time is """	,   exec_time / 100      )
   return exec_time

def 							_snake_case			(      ):




   """simple docstring"""







   matrix_exponentiation_time()
   simple_fibonacci_time()


if __name__ == "__main__":
 main()

