'''simple docstring'''





SCREAMING_SNAKE_CASE_:     str  =2_56
# Modulus to hash a string
SCREAMING_SNAKE_CASE_:     int  =1_00_00_03





def 	lowerCAmelCase_				(					snake_case_       : str					,    snake_case_       : str			)    ->      bool:


     '''simple docstring'''




     UpperCAmelCase_           =   len(snake_case_			)
     UpperCAmelCase_           =   len(snake_case_			)
     if p_len > t_len:
          return False

     UpperCAmelCase_           =   0
     UpperCAmelCase_           =   0
     UpperCAmelCase_           =   1

     # Calculating the hash of pattern and substring of text
     for i in range(snake_case_			):
          UpperCAmelCase_           =   (ord(pattern[i]			) + p_hash * alphabet_size) % modulus
          UpperCAmelCase_           =   (ord(text[i]			) + text_hash * alphabet_size) % modulus
          if i == p_len - 1:
               continue
          UpperCAmelCase_           =   (modulus_power * alphabet_size) % modulus

     for i in range(0					,    t_len - p_len + 1			):
          if text_hash == p_hash and text[i : i + p_len] == pattern:
               return True
          if i == t_len - p_len:
               continue
          # Calculate the https://en.wikipedia.org/wiki/Rolling_hash
          UpperCAmelCase_           =   (
              (text_hash - ord(text[i]			) * modulus_power) * alphabet_size
              + ord(text[i + p_len]			)
          ) % modulus
     return False





def 	lowerCAmelCase_				(					)    ->      None:


     '''simple docstring'''




     UpperCAmelCase_           =   "abc1abc12"
     UpperCAmelCase_           =   "alskfjaldsabc1abc1abc12k23adsfabcabc"
     UpperCAmelCase_           =   "alskfjaldsk23adsfabcabc"
     assert rabin_karp(snake_case_					,    snake_case_			) and not rabin_karp(snake_case_					,    snake_case_			)

     # Test 2)
     UpperCAmelCase_           =   "ABABX"
     UpperCAmelCase_           =   "ABABZABABYABABX"
     assert rabin_karp(snake_case_					,    snake_case_			)

     # Test 3)
     UpperCAmelCase_           =   "AAAB"
     UpperCAmelCase_           =   "ABAAAAAB"
     assert rabin_karp(snake_case_					,    snake_case_			)

     # Test 4)
     UpperCAmelCase_           =   "abcdabcy"
     UpperCAmelCase_           =   "abcxabcdabxabcdabcdabcy"
     assert rabin_karp(snake_case_					,    snake_case_			)

     # Test 5)
     UpperCAmelCase_           =   "Lü"
     UpperCAmelCase_           =   "Lüsai"
     assert rabin_karp(snake_case_					,    snake_case_			)
     UpperCAmelCase_           =   "Lue"
     assert not rabin_karp(snake_case_					,    snake_case_			)
     print("Success."			)


if __name__ == "__main__":
    test_rabin_karp()






'''simple docstring'''




def 		lowerCAmelCase_				(   snake_case__ = 10						):




    '''simple docstring'''



    if not isinstance(snake_case__		,				snake_case__						) or n < 0:
        raise ValueError('''Invalid input'''						)
    A       :   List[str]					=						10**n
    A       :   Tuple					=						2_8433 * (pow(2		,				783_0457		,				snake_case__						)) + 1
    return str(number % modulus						)


if __name__ == "__main__":
      from doctest import testmod

      testmod()
      print(f'''{solution(10) = }''')




