

"""simple docstring"""






import timeit






class       _UpperCAmelCase     :
			def __init__(						self ,						_A       )      ->      Tuple:






				'''simple docstring'''







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






				'''simple docstring'''







				_UpperCAmelCase      :							Optional[int]       =   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  UpperCamelCase   (     _lowerCAmelCase       :  int,					_lowerCAmelCase       :  List[str]	)			->     Tuple:
	_UpperCAmelCase      :							Union[str, Any]       =   Matrix([[1, 0], [0, 1]]	)
	while b > 0:
		if b & 1:
			matrix *= a
		a *= a
		b >>= 1
	return matrix
def  UpperCamelCase   (     _lowerCAmelCase       :  str,					_lowerCAmelCase       :  Optional[int],					_lowerCAmelCase       :  List[str]	)			->     int:
	# Trivial Cases
	if n == 1:
		return fa
	elif n == 2:
		return fa
	_UpperCAmelCase      :							Optional[int]       =   Matrix([[1, 1], [1, 0]]	)
	_UpperCAmelCase      :							Tuple       =   modular_exponentiation(_lowerCAmelCase,					n - 2	)
	return fa * matrix.t[0][0] + fa * matrix.t[0][1]
def  UpperCamelCase   (     _lowerCAmelCase       :  List[Any],					_lowerCAmelCase       :  List[Any],					_lowerCAmelCase       :  Optional[Any]	)			->     int:
	# Trivial Cases
	if n == 1:
		return fa
	elif n == 2:
		return fa

	_UpperCAmelCase      :							Dict       =   fa
	_UpperCAmelCase      :							str       =   fa
	n -= 2

	while n > 0:
		_UpperCAmelCase  ,				_UpperCAmelCase      :							Dict       =   fn_a + fn_a, fn_a
		n -= 1

	return fn_a
def  UpperCamelCase   (     )			->     int:
	_UpperCAmelCase      :							List[str]       =   """
from random import randint
from __main__ import fibonacci_with_matrix_exponentiation
"""
	_UpperCAmelCase      :							Union[str, Any]       =   """fibonacci_with_matrix_exponentiation(randint(1,70000), 1, 1)"""
	_UpperCAmelCase      :							int       =   timeit.timeit(setup=_lowerCAmelCase,					stmt=_lowerCAmelCase,					number=100	)
	print("""With matrix exponentiation the average execution time is """,					exec_time / 100	)
	return exec_time
def  UpperCamelCase   (     )			->     List[Any]:
	_UpperCAmelCase      :							Union[str, Any]       =   """
from random import randint
from __main__ import simple_fibonacci
"""
	_UpperCAmelCase      :							Optional[Any]       =   """simple_fibonacci(randint(1,70000), 1, 1)"""
	_UpperCAmelCase      :							str       =   timeit.timeit(setup=_lowerCAmelCase,					stmt=_lowerCAmelCase,					number=100	)
	print(
	    """Without matrix exponentiation the average execution time is """,					exec_time / 100	)
	return exec_time
def  UpperCamelCase   (     )			->     Optional[Any]:
	matrix_exponentiation_time()
	simple_fibonacci_time()


if __name__ == "__main__":
						main()








"""simple docstring"""






from typing import TYPE_CHECKING

from ...utils import (
    OptionalDependencyNotAvailable,
    _LazyModule,
    is_flax_available,
    is_tf_available,
    is_torch_available,
)


lowerCamelCase__			:					Union[str, Any]							  =					{
    '''configuration_unispeech_sat''': ['''UNISPEECH_SAT_PRETRAINED_CONFIG_ARCHIVE_MAP''', '''UniSpeechSatConfig'''],
}

try:
						if not is_torch_available():
												raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
						pass
else:
						lowerCamelCase__			:					List[str]							  =					[
						    '''UNISPEECH_SAT_PRETRAINED_MODEL_ARCHIVE_LIST''',
						    '''UniSpeechSatForAudioFrameClassification''',
						    '''UniSpeechSatForCTC''',
						    '''UniSpeechSatForPreTraining''',
						    '''UniSpeechSatForSequenceClassification''',
						    '''UniSpeechSatForXVector''',
						    '''UniSpeechSatModel''',
						    '''UniSpeechSatPreTrainedModel''',
						]

if TYPE_CHECKING:
						from .configuration_unispeech_sat import UNISPEECH_SAT_PRETRAINED_CONFIG_ARCHIVE_MAP, UniSpeechSatConfig

						try:
												if not is_torch_available():
																		raise OptionalDependencyNotAvailable()
						except OptionalDependencyNotAvailable:
												pass
						else:
												from .modeling_unispeech_sat import (
												    UNISPEECH_SAT_PRETRAINED_MODEL_ARCHIVE_LIST,
												    UniSpeechSatForAudioFrameClassification,
												    UniSpeechSatForCTC,
												    UniSpeechSatForPreTraining,
												    UniSpeechSatForSequenceClassification,
												    UniSpeechSatForXVector,
												    UniSpeechSatModel,
												    UniSpeechSatPreTrainedModel,
												)

else:
						import sys

						lowerCamelCase__			:					Any							  =					_LazyModule(__name__, globals()['''__file__'''], _import_structure, module_spec=__spec__)





