





"""simple docstring"""
import json
import os
import re
import shutil
import tempfile
import unittest
from typing import Tuple

from transformers import AddedToken, BatchEncoding, ByTaTokenizer
from transformers.utils import cached_property, is_tf_available, is_torch_available

from ...test_tokenization_common import TokenizerTesterMixin


if is_torch_available():
  lowerCamelCase_								=		"pt"
elif is_tf_available():
  lowerCamelCase_								=		"tf"
else:
  lowerCamelCase_								=		"jax"






class 					_SCREAMING_SNAKE_CASE(   A    ,	unittest.TestCase  ):
       SCREAMING_SNAKE_CASE_   :      List[str]							=  ByTaTokenizer
       SCREAMING_SNAKE_CASE_   :      Dict							=  False




       def     _UpperCamelCase     (						self							)			->      Optional[Any]:





             """simple docstring"""






             super().setUp()
             __SCREAMING_SNAKE_CASE   :Tuple						=  ByTaTokenizer()
             tokenizer.save_pretrained(self.tmpdirname							)




       @cached_property
       def     _UpperCamelCase     (						self							)			->      Tuple:





             """simple docstring"""






             return ByTaTokenizer.from_pretrained('''google/byt5-small'''							)




       def     _UpperCamelCase     (						self		,**SCREAMING_SNAKE_CASE__							)			->      ByTaTokenizer:





             """simple docstring"""






             return self.tokenizer_class.from_pretrained(self.tmpdirname		,**SCREAMING_SNAKE_CASE__							)




       def     _UpperCamelCase     (						self		,SCREAMING_SNAKE_CASE__		,SCREAMING_SNAKE_CASE__=False		,SCREAMING_SNAKE_CASE__=20		,SCREAMING_SNAKE_CASE__=5							)			->      Tuple[str, list]:





             """simple docstring"""






             __SCREAMING_SNAKE_CASE   :Tuple						=  []
             for i in range(len(SCREAMING_SNAKE_CASE__							)							):
                   try:
                         __SCREAMING_SNAKE_CASE   :str						=  tokenizer.decode([i]		,clean_up_tokenization_spaces=SCREAMING_SNAKE_CASE__							)
                   except UnicodeDecodeError:
                         pass
                   toks.append((i, tok)							)

             __SCREAMING_SNAKE_CASE   :Optional[int]						=  list(filter(lambda SCREAMING_SNAKE_CASE__							: re.match(R'''^[ a-zA-Z]+$'''		,t[1]							)		,SCREAMING_SNAKE_CASE__							)							)
             __SCREAMING_SNAKE_CASE   :List[Any]						=  list(filter(lambda SCREAMING_SNAKE_CASE__							: [t[0]] == tokenizer.encode(t[1]		,add_special_tokens=SCREAMING_SNAKE_CASE__							)		,SCREAMING_SNAKE_CASE__							)							)
             if max_length is not None and len(SCREAMING_SNAKE_CASE__							) > max_length:
                   __SCREAMING_SNAKE_CASE   :Union[str, Any]						=  toks[:max_length]
             if min_length is not None and len(SCREAMING_SNAKE_CASE__							) < min_length and len(SCREAMING_SNAKE_CASE__							) > 0:
                   while len(SCREAMING_SNAKE_CASE__							) < min_length:
                         __SCREAMING_SNAKE_CASE   :Union[str, Any]						=  toks + toks
        # toks_str = [t[1] for t in toks]
             __SCREAMING_SNAKE_CASE   :str						=  [t[0] for t in toks]

             # Ensure consistency
             __SCREAMING_SNAKE_CASE   :List[Any]						=  tokenizer.decode(SCREAMING_SNAKE_CASE__		,clean_up_tokenization_spaces=SCREAMING_SNAKE_CASE__							)
             if " " not in output_txt and len(SCREAMING_SNAKE_CASE__							) > 1:
                   __SCREAMING_SNAKE_CASE   :Optional[int]						=  (
                       tokenizer.decode([toks_ids[0]]		,clean_up_tokenization_spaces=SCREAMING_SNAKE_CASE__							)
                       + ''' '''
                       + tokenizer.decode(toks_ids[1:]		,clean_up_tokenization_spaces=SCREAMING_SNAKE_CASE__							)
                   )
             if with_prefix_space:
                   __SCREAMING_SNAKE_CASE   :List[str]						=  ''' ''' + output_txt
             __SCREAMING_SNAKE_CASE   :int						=  tokenizer.encode(SCREAMING_SNAKE_CASE__		,add_special_tokens=SCREAMING_SNAKE_CASE__							)
             return output_txt, output_ids




       def     _UpperCamelCase     (						self							)			->      List[Any]:





             """simple docstring"""






             __SCREAMING_SNAKE_CASE   :str						=  self.ta_base_tokenizer
             __SCREAMING_SNAKE_CASE   :Optional[int]						=  tokenizer(['''hi</s>''', '''I went to the gym</s>''', '''</s>''']							)
             __SCREAMING_SNAKE_CASE   :List[Any]						=  tokenizer(['''hi''', '''I went to the gym''', '''''']							)
             self.assertListEqual(batch_with_eos_added['''input_ids''']		,batch_without_eos_added['''input_ids''']							)




       def     _UpperCamelCase     (						self							)			->      Any:





             """simple docstring"""






             __SCREAMING_SNAKE_CASE   :Union[str, Any]						=  self.ta_base_tokenizer
             __SCREAMING_SNAKE_CASE   :Optional[int]						=  '''Unicode €.'''
             __SCREAMING_SNAKE_CASE   :List[Any]						=  tokenizer(SCREAMING_SNAKE_CASE__							)
             __SCREAMING_SNAKE_CASE   :List[str]						=  [88, 1_13, 1_08, 1_02, 1_14, 1_03, 1_04, 35, 2_29, 1_33, 1_75, 49, 1]
             self.assertEqual(encoded['''input_ids''']		,SCREAMING_SNAKE_CASE__							)

             # decoding
             __SCREAMING_SNAKE_CASE   :Optional[Any]						=  tokenizer.decode(SCREAMING_SNAKE_CASE__							)
             self.assertEqual(SCREAMING_SNAKE_CASE__		,'''Unicode €.</s>'''							)

             __SCREAMING_SNAKE_CASE   :Dict						=  tokenizer('''e è é ê ë'''							)
             __SCREAMING_SNAKE_CASE   :str						=  [1_04, 35, 1_98, 1_71, 35, 1_98, 1_72, 35, 1_98, 1_73, 35, 1_98, 1_74, 1]
             self.assertEqual(encoded['''input_ids''']		,SCREAMING_SNAKE_CASE__							)
             # decoding
             __SCREAMING_SNAKE_CASE   :Optional[int]						=  tokenizer.decode(SCREAMING_SNAKE_CASE__							)
             self.assertEqual(SCREAMING_SNAKE_CASE__		,'''e è é ê ë</s>'''							)

             # encode/decode, but with `encode` instead of `__call__`
             self.assertEqual(tokenizer.decode(tokenizer.encode('''e è é ê ë'''							)							)		,'''e è é ê ë</s>'''							)




       def     _UpperCamelCase     (						self							)			->      List[Any]:





             """simple docstring"""






             __SCREAMING_SNAKE_CASE   :List[str]						=  self.ta_base_tokenizer
             __SCREAMING_SNAKE_CASE   :Any						=  ['''A long paragraph for summarization.''', '''Another paragraph for summarization.''']
             # fmt: off
             __SCREAMING_SNAKE_CASE   :int						=  [68, 35, 1_11, 1_14, 1_13, 1_06, 35, 1_15, 1_00, 1_17, 1_00, 1_06, 1_17, 1_00, 1_15, 1_07, 35, 1_05, 1_14, 1_17, 35, 1_18, 1_20, 1_12, 1_12, 1_00, 1_17, 1_08, 1_25, 1_00, 1_19, 1_08, 1_14, 1_13, 49, 1, 0]
             # fmt: on
             __SCREAMING_SNAKE_CASE   :int						=  tokenizer(SCREAMING_SNAKE_CASE__		,padding=SCREAMING_SNAKE_CASE__		,return_tensors=SCREAMING_SNAKE_CASE__							)
             self.assertIsInstance(SCREAMING_SNAKE_CASE__		,SCREAMING_SNAKE_CASE__							)

             if FRAMEWORK != "jax":
                   __SCREAMING_SNAKE_CASE   :Optional[int]						=  list(batch.input_ids.numpy()[0]							)
             else:
                   __SCREAMING_SNAKE_CASE   :int						=  list(batch.input_ids.tolist()[0]							)

             self.assertListEqual(SCREAMING_SNAKE_CASE__		,SCREAMING_SNAKE_CASE__							)

             self.assertEqual((2, 37)		,batch.input_ids.shape							)
             self.assertEqual((2, 37)		,batch.attention_mask.shape							)




       def     _UpperCamelCase     (						self							)			->      int:





             """simple docstring"""






             __SCREAMING_SNAKE_CASE   :Union[str, Any]						=  self.ta_base_tokenizer
             __SCREAMING_SNAKE_CASE   :Optional[Any]						=  ['''A long paragraph for summarization.''', '''Another paragraph for summarization.''']
             __SCREAMING_SNAKE_CASE   :List[str]						=  tokenizer(SCREAMING_SNAKE_CASE__		,padding=SCREAMING_SNAKE_CASE__		,return_tensors=SCREAMING_SNAKE_CASE__							)
             # check if input_ids are returned and no decoder_input_ids
             self.assertIn('''input_ids'''		,SCREAMING_SNAKE_CASE__							)
             self.assertIn('''attention_mask'''		,SCREAMING_SNAKE_CASE__							)
             self.assertNotIn('''decoder_input_ids'''		,SCREAMING_SNAKE_CASE__							)
             self.assertNotIn('''decoder_attention_mask'''		,SCREAMING_SNAKE_CASE__							)




       def     _UpperCamelCase     (						self							)			->      str:





             """simple docstring"""






             __SCREAMING_SNAKE_CASE   :Tuple						=  self.ta_base_tokenizer
             __SCREAMING_SNAKE_CASE   :int						=  [
                 '''Summary of the text.''',
                 '''Another summary.''',
             ]
             __SCREAMING_SNAKE_CASE   :Tuple						=  tokenizer(
                 text_target=SCREAMING_SNAKE_CASE__		,max_length=32		,padding='''max_length'''		,truncation=SCREAMING_SNAKE_CASE__		,return_tensors=SCREAMING_SNAKE_CASE__							)
             self.assertEqual(32		,targets['''input_ids'''].shape[1]							)




       def     _UpperCamelCase     (						self							)			->      Optional[Any]:





             """simple docstring"""






             __SCREAMING_SNAKE_CASE   :Tuple						=  self.ta_base_tokenizer
             __SCREAMING_SNAKE_CASE   :Optional[int]						=  ['''A long paragraph for summarization. </s>''']
             __SCREAMING_SNAKE_CASE   :Any						=  ['''Summary of the text. </s>''']
             # fmt: off
             __SCREAMING_SNAKE_CASE   :Tuple						=  [68, 35, 1_11, 1_14, 1_13, 1_06, 35, 1_15, 1_00, 1_17, 1_00, 1_06, 1_17, 1_00, 1_15, 1_07, 35, 1_05, 1_14, 1_17, 35, 1_18, 1_20, 1_12, 1_12, 1_00, 1_17, 1_08, 1_25, 1_00, 1_19, 1_08, 1_14, 1_13, 49, 35, 1]
             __SCREAMING_SNAKE_CASE   :int						=  [86, 1_20, 1_12, 1_12, 1_00, 1_17, 1_24, 35, 1_14, 1_05, 35, 1_19, 1_07, 1_04, 35, 1_19, 1_04, 1_23, 1_19, 49, 35, 1]
             # fmt: on

             __SCREAMING_SNAKE_CASE   :str						=  tokenizer(SCREAMING_SNAKE_CASE__		,text_target=SCREAMING_SNAKE_CASE__							)

             self.assertEqual(SCREAMING_SNAKE_CASE__		,batch['''input_ids'''][0]							)
             self.assertEqual(SCREAMING_SNAKE_CASE__		,batch['''labels'''][0]							)




       def     _UpperCamelCase     (						self							)			->      Optional[int]:





             """simple docstring"""






             __SCREAMING_SNAKE_CASE   :Union[str, Any]						=  self.get_tokenizers()
             for tokenizer in tokenizers:
                   with self.subTest(f'''{tokenizer.__class__.__name__}'''							):
                         self.assertNotEqual(tokenizer.model_max_length		,42							)

        # Now let's start the test
             __SCREAMING_SNAKE_CASE   :Optional[int]						=  self.get_tokenizers()
             for tokenizer in tokenizers:
                   with self.subTest(f'''{tokenizer.__class__.__name__}'''							):
                         # Isolate this from the other tests because we save additional tokens/etc
                         __SCREAMING_SNAKE_CASE   :Tuple						=  tempfile.mkdtemp()

                         __SCREAMING_SNAKE_CASE   :Tuple						=  ''' He is very happy, UNwant\u00E9d,running'''
                         __SCREAMING_SNAKE_CASE   :Optional[Any]						=  tokenizer.encode(SCREAMING_SNAKE_CASE__		,add_special_tokens=SCREAMING_SNAKE_CASE__							)
                         tokenizer.save_pretrained(SCREAMING_SNAKE_CASE__							)

                         __SCREAMING_SNAKE_CASE   :Union[str, Any]						=  tokenizer.__class__.from_pretrained(SCREAMING_SNAKE_CASE__							)
                         __SCREAMING_SNAKE_CASE   :int						=  after_tokenizer.encode(SCREAMING_SNAKE_CASE__		,add_special_tokens=SCREAMING_SNAKE_CASE__							)
                         self.assertListEqual(SCREAMING_SNAKE_CASE__		,SCREAMING_SNAKE_CASE__							)

                         shutil.rmtree(SCREAMING_SNAKE_CASE__							)

             __SCREAMING_SNAKE_CASE   :Optional[Any]						=  self.get_tokenizers(model_max_length=42							)
             for tokenizer in tokenizers:
                   with self.subTest(f'''{tokenizer.__class__.__name__}'''							):
                         # Isolate this from the other tests because we save additional tokens/etc
                         __SCREAMING_SNAKE_CASE   :Tuple						=  tempfile.mkdtemp()

                         __SCREAMING_SNAKE_CASE   :Optional[Any]						=  ''' He is very happy, UNwant\u00E9d,running'''
                         tokenizer.add_tokens(['''bim''', '''bambam''']							)
                         __SCREAMING_SNAKE_CASE   :Any						=  tokenizer.additional_special_tokens
                         additional_special_tokens.append('''new_additional_special_token'''							)
                         tokenizer.add_special_tokens({'''additional_special_tokens''': additional_special_tokens}							)
                         __SCREAMING_SNAKE_CASE   :Optional[int]						=  tokenizer.encode(SCREAMING_SNAKE_CASE__		,add_special_tokens=SCREAMING_SNAKE_CASE__							)
                         tokenizer.save_pretrained(SCREAMING_SNAKE_CASE__							)

                         __SCREAMING_SNAKE_CASE   :Optional[Any]						=  tokenizer.__class__.from_pretrained(SCREAMING_SNAKE_CASE__							)
                         __SCREAMING_SNAKE_CASE   :Optional[Any]						=  after_tokenizer.encode(SCREAMING_SNAKE_CASE__		,add_special_tokens=SCREAMING_SNAKE_CASE__							)
                         self.assertListEqual(SCREAMING_SNAKE_CASE__		,SCREAMING_SNAKE_CASE__							)
                         self.assertIn('''new_additional_special_token'''		,after_tokenizer.additional_special_tokens							)
                         self.assertEqual(after_tokenizer.model_max_length		,42							)

                         __SCREAMING_SNAKE_CASE   :str						=  tokenizer.__class__.from_pretrained(SCREAMING_SNAKE_CASE__		,model_max_length=43							)
                         self.assertEqual(tokenizer.model_max_length		,43							)

                         shutil.rmtree(SCREAMING_SNAKE_CASE__							)




       def     _UpperCamelCase     (						self							)			->      int:





             """simple docstring"""






             __SCREAMING_SNAKE_CASE   :str						=  []
             if self.test_slow_tokenizer:
                   tokenizer_list.append((self.tokenizer_class, self.get_tokenizer())							)

             if self.test_rust_tokenizer:
                   tokenizer_list.append((self.rust_tokenizer_class, self.get_rust_tokenizer())							)

             for tokenizer_class, tokenizer_utils in tokenizer_list:
                   with tempfile.TemporaryDirectory() as tmp_dir:
                         tokenizer_utils.save_pretrained(SCREAMING_SNAKE_CASE__							)

                         with open(os.path.join(SCREAMING_SNAKE_CASE__		,'''special_tokens_map.json'''							)		,encoding='''utf-8'''							) as json_file:
                               __SCREAMING_SNAKE_CASE   :Any						=  json.load(SCREAMING_SNAKE_CASE__							)

                         with open(os.path.join(SCREAMING_SNAKE_CASE__		,'''tokenizer_config.json'''							)		,encoding='''utf-8'''							) as json_file:
                               __SCREAMING_SNAKE_CASE   :Optional[Any]						=  json.load(SCREAMING_SNAKE_CASE__							)

                         __SCREAMING_SNAKE_CASE   :Tuple						=  [f'''<extra_id_{i}>''' for i in range(1_25							)]

                         __SCREAMING_SNAKE_CASE   :Tuple						=  added_tokens_extra_ids + [
                             '''an_additional_special_token'''
                         ]
                         __SCREAMING_SNAKE_CASE   :int						=  added_tokens_extra_ids + [
                             '''an_additional_special_token'''
                         ]

                         with open(os.path.join(SCREAMING_SNAKE_CASE__		,'''special_tokens_map.json'''							)		,'''w'''		,encoding='''utf-8'''							) as outfile:
                               json.dump(SCREAMING_SNAKE_CASE__		,SCREAMING_SNAKE_CASE__							)
                         with open(os.path.join(SCREAMING_SNAKE_CASE__		,'''tokenizer_config.json'''							)		,'''w'''		,encoding='''utf-8'''							) as outfile:
                               json.dump(SCREAMING_SNAKE_CASE__		,SCREAMING_SNAKE_CASE__							)

                         # the following checks allow us to verify that our test works as expected, i.e. that the tokenizer takes
                         # into account the new value of additional_special_tokens given in the "tokenizer_config.json" and
                         # "special_tokens_map.json" files
                         __SCREAMING_SNAKE_CASE   :Dict						=  tokenizer_class.from_pretrained(
                             SCREAMING_SNAKE_CASE__		,)
                         self.assertIn(
                             '''an_additional_special_token'''		,tokenizer_without_change_in_init.additional_special_tokens							)
                         # self.assertIn("an_additional_special_token",tokenizer_without_change_in_init.get_vocab()) # ByT5Tokenization no vocab
                         self.assertEqual(
                             ['''an_additional_special_token''']		,tokenizer_without_change_in_init.convert_ids_to_tokens(
                                 tokenizer_without_change_in_init.convert_tokens_to_ids(['''an_additional_special_token''']							)							)		,)

                         # Now we test that we can change the value of additional_special_tokens in the from_pretrained
                         __SCREAMING_SNAKE_CASE   :Optional[Any]						=  added_tokens_extra_ids + [AddedToken('''a_new_additional_special_token'''		,lstrip=SCREAMING_SNAKE_CASE__							)]
                         __SCREAMING_SNAKE_CASE   :str						=  tokenizer_class.from_pretrained(
                             SCREAMING_SNAKE_CASE__		,additional_special_tokens=SCREAMING_SNAKE_CASE__		,)

                         self.assertIn('''a_new_additional_special_token'''		,tokenizer.additional_special_tokens							)
                         self.assertEqual(
                             ['''a_new_additional_special_token''']		,tokenizer.convert_ids_to_tokens(
                                 tokenizer.convert_tokens_to_ids(['''a_new_additional_special_token''']							)							)		,)




       def     _UpperCamelCase     (						self							)			->      Tuple:





             """simple docstring"""






             __SCREAMING_SNAKE_CASE   :int						=  []
             if self.test_slow_tokenizer:
                   tokenizer_list.append((self.tokenizer_class, self.get_tokenizer())							)

             if self.test_rust_tokenizer:
                   tokenizer_list.append((self.rust_tokenizer_class, self.get_rust_tokenizer())							)

             for tokenizer_class, tokenizer_utils in tokenizer_list:
                   with tempfile.TemporaryDirectory() as tmp_dir:
                         tokenizer_utils.save_pretrained(SCREAMING_SNAKE_CASE__							)

                         __SCREAMING_SNAKE_CASE   :Tuple						=  tokenizer_class.from_pretrained(SCREAMING_SNAKE_CASE__							)

                         self.assertTrue(tokenizer.decode([2_55]							) == ''''''							)




       def     _UpperCamelCase     (						self							)			->      Any:





             """simple docstring"""






             pass




       def     _UpperCamelCase     (						self							)			->      int:





             """simple docstring"""






             pass




       def     _UpperCamelCase     (						self							)			->      Tuple:





             """simple docstring"""






             pass




       def     _UpperCamelCase     (						self							)			->      Optional[int]:





             """simple docstring"""






             pass




       def     _UpperCamelCase     (						self							)			->      Optional[int]:





             """simple docstring"""






             __SCREAMING_SNAKE_CASE   :List[str]						=  self.get_tokenizers(fast=SCREAMING_SNAKE_CASE__		,do_lower_case=SCREAMING_SNAKE_CASE__							)
             for tokenizer in tokenizers:
                   with self.subTest(f'''{tokenizer.__class__.__name__}'''							):
                         __SCREAMING_SNAKE_CASE   :Any						=  ['''t''', '''h''', '''i''', '''s''', ''' ''', '''i''', '''s''', ''' ''', '''a''', ''' ''', '''t''', '''e''', '''x''', '''t''', '''</s>''']
                         __SCREAMING_SNAKE_CASE   :int						=  tokenizer.convert_tokens_to_string(SCREAMING_SNAKE_CASE__							)

                         self.assertIsInstance(SCREAMING_SNAKE_CASE__		,SCREAMING_SNAKE_CASE__							)




       def     _UpperCamelCase     (						self							)			->      Tuple:





             """simple docstring"""






             __SCREAMING_SNAKE_CASE   :Optional[Any]						=  self.get_tokenizers()
             for tokenizer in tokenizers:
                   with self.subTest(f'''{tokenizer.__class__.__name__}'''							):
                         __SCREAMING_SNAKE_CASE   :Optional[Any]						=  [
                             '''bos_token''',
                             '''eos_token''',
                             '''unk_token''',
                             '''sep_token''',
                             '''pad_token''',
                             '''cls_token''',
                             '''mask_token''',
                         ]

                         __SCREAMING_SNAKE_CASE   :Any						=  0
                         __SCREAMING_SNAKE_CASE   :Optional[int]						=  tokenizer.convert_ids_to_tokens(
                             SCREAMING_SNAKE_CASE__		,skip_special_tokens=SCREAMING_SNAKE_CASE__							)

                         for attr in attributes_list:
                               setattr(SCREAMING_SNAKE_CASE__		,attr + '''_id'''		,SCREAMING_SNAKE_CASE__							)
                               self.assertEqual(getattr(SCREAMING_SNAKE_CASE__		,SCREAMING_SNAKE_CASE__							)		,SCREAMING_SNAKE_CASE__							)
                               self.assertEqual(getattr(SCREAMING_SNAKE_CASE__		,attr + '''_id'''							)		,SCREAMING_SNAKE_CASE__							)

                               setattr(SCREAMING_SNAKE_CASE__		,attr + '''_id'''		,SCREAMING_SNAKE_CASE__							)
                               self.assertEqual(getattr(SCREAMING_SNAKE_CASE__		,SCREAMING_SNAKE_CASE__							)		,SCREAMING_SNAKE_CASE__							)
                               self.assertEqual(getattr(SCREAMING_SNAKE_CASE__		,attr + '''_id'''							)		,SCREAMING_SNAKE_CASE__							)

                         setattr(SCREAMING_SNAKE_CASE__		,'''additional_special_tokens_ids'''		,[]							)
                         self.assertListEqual(getattr(SCREAMING_SNAKE_CASE__		,'''additional_special_tokens'''							)		,[]							)
                         self.assertListEqual(getattr(SCREAMING_SNAKE_CASE__		,'''additional_special_tokens_ids'''							)		,[]							)

                         setattr(SCREAMING_SNAKE_CASE__		,'''additional_special_tokens_ids'''		,[token_id_to_test_setters]							)
                         self.assertListEqual(getattr(SCREAMING_SNAKE_CASE__		,'''additional_special_tokens'''							)		,[token_to_test_setters]							)
                         self.assertListEqual(getattr(SCREAMING_SNAKE_CASE__		,'''additional_special_tokens_ids'''							)		,[token_id_to_test_setters]							)






"""simple docstring"""
def      __lowerCamelCase   (							a_     :		int ,   a_     :		str							)			->      Optional[int]:
      __SCREAMING_SNAKE_CASE   :Optional[int]						=  [1]
      for i in range(2 ,   a_							):
            factorials.append(factorials[-1] * i							)
      assert 0 <= k < factorials[-1] * n, "k out of bounds"

      __SCREAMING_SNAKE_CASE   :List[str]						=  []
      __SCREAMING_SNAKE_CASE   :Optional[Any]						=  list(range(a_							)							)

      # Find permutation
      while factorials:
            __SCREAMING_SNAKE_CASE   :Optional[int]						=  factorials.pop()
            __SCREAMING_SNAKE_CASE				,__SCREAMING_SNAKE_CASE   :Dict						=  divmod(a_ ,   a_							)
            permutation.append(elements[number]							)
            elements.remove(elements[number]							)
      permutation.append(elements[0]							)

      return permutation


if __name__ == "__main__":
  import doctest

  doctest.testmod()