

from collections.abc import Generator
from math import sin
def      _lowerCAmelCase(	__A			):
  if len(__A			) != 32:
    raise ValueError("Input must be of length 32"			)

  UpperCAmelCase					      =  B""
  for i in [3, 2, 1, 0]:
    little_endian += string_aa[8 * i : 8 * i + 8]
  return little_endian
def      _lowerCAmelCase(	__A			):
  if i < 0:
    raise ValueError("Input must be non-negative"			)

  UpperCAmelCase					      =  format(__A   ,       "08x"			)[-8:]
  UpperCAmelCase					      =  B""
  for i in [3, 2, 1, 0]:
    little_endian_hex += hex_rep[2 * i : 2 * i + 2].encode("utf-8"			)
  return little_endian_hex
def      _lowerCAmelCase(	__A			):
  UpperCAmelCase					      =  B""
  for char in message:
    bit_string += format(__A   ,       "08b"			).encode("utf-8"			)
  UpperCAmelCase					      =  format(len(__A			)   ,       "064b"			).encode("utf-8"			)

  # Pad bit_string to a multiple of 512 chars
  bit_string += b"1"
  while len(__A			) % 512 != 448:
    bit_string += b"0"
  bit_string += to_little_endian(start_len[32:]			) + to_little_endian(start_len[:32]			)

  return bit_string
def      _lowerCAmelCase(	__A			):
  if len(__A			) % 512 != 0:
    raise ValueError("Input must have length that's a multiple of 512"			)

  for pos in range(0   ,       len(__A			)   ,       512			):
    UpperCAmelCase					      =  bit_string[pos : pos + 512]
    UpperCAmelCase					      =  []
    for i in range(0   ,       512   ,       32			):
      block_words.append(int(to_little_endian(block[i : i + 32]			)   ,       2			)			)
    yield block_words
def      _lowerCAmelCase(	__A			):
  if i < 0:
    raise ValueError("Input must be non-negative"			)

  UpperCAmelCase					      =  format(__A   ,       "032b"			)
  UpperCAmelCase					      =  ""
  for c in i_str:
    new_str += "1" if c == "0" else "0"
  return int(__A   ,       2			)
def      _lowerCAmelCase(	__A   ,       __A			):
  return (a + b) % 2**32
def      _lowerCAmelCase(	__A   ,       __A			):
  if i < 0:
    raise ValueError("Input must be non-negative"			)
  if shift < 0:
    raise ValueError("Shift must be non-negative"			)
  return ((i << shift) ^ (i >> (32 - shift))) % 2**32
def      _lowerCAmelCase(	__A			):
  UpperCAmelCase					      =  preprocess(__A			)

  UpperCAmelCase					      =  [int(2**32 * abs(sin(i + 1			)			)			) for i in range(64			)]

  # Starting states
  UpperCAmelCase					      =  0x6_7_4_5_2_3_0_1
  UpperCAmelCase					      =  0xE_F_C_D_A_B_8_9
  UpperCAmelCase					      =  0x9_8_B_A_D_C_F_E
  UpperCAmelCase					      =  0x1_0_3_2_5_4_7_6

  UpperCAmelCase					      =  [
      7,
      12,
      17,
      22,
      7,
      12,
      17,
      22,
      7,
      12,
      17,
      22,
      7,
      12,
      17,
      22,
      5,
      9,
      14,
      20,
      5,
      9,
      14,
      20,
      5,
      9,
      14,
      20,
      5,
      9,
      14,
      20,
      4,
      11,
      16,
      23,
      4,
      11,
      16,
      23,
      4,
      11,
      16,
      23,
      4,
      11,
      16,
      23,
      6,
      10,
      15,
      21,
      6,
      10,
      15,
      21,
      6,
      10,
      15,
      21,
      6,
      10,
      15,
      21,
  ]

  # Process bit string in chunks, each with 16 32-char words
  for block_words in get_block_words(__A			):
    UpperCAmelCase					      =  aa
    UpperCAmelCase					      =  ba
    UpperCAmelCase					      =  ca
    UpperCAmelCase					      =  da

    # Hash current chunk
    for i in range(64			):
      if i <= 15:
        # f = (b & c) | (not_32(b) & d)     # Alternate definition for f
        UpperCAmelCase					      =  d ^ (b & (c ^ d))
        UpperCAmelCase					      =  i
      elif i <= 31:
        # f = (d & b) | (not_32(d) & c)     # Alternate definition for f
        UpperCAmelCase					      =  c ^ (d & (b ^ c))
        UpperCAmelCase					      =  (5 * i + 1) % 16
      elif i <= 47:
        UpperCAmelCase					      =  b ^ c ^ d
        UpperCAmelCase					      =  (3 * i + 5) % 16
      else:
        UpperCAmelCase					      =  c ^ (b | not_aa(__A			))
        UpperCAmelCase					      =  (7 * i) % 16
      UpperCAmelCase					      =  (f + a + added_consts[i] + block_words[g]) % 2**32
      UpperCAmelCase					      =  d
      UpperCAmelCase					      =  c
      UpperCAmelCase					      =  b
      UpperCAmelCase					      =  sum_aa(__A   ,       left_rotate_aa(__A   ,       shift_amounts[i]			)			)

    # Add hashed chunk to running total
    UpperCAmelCase					      =  sum_aa(__A   ,       __A			)
    UpperCAmelCase					      =  sum_aa(__A   ,       __A			)
    UpperCAmelCase					      =  sum_aa(__A   ,       __A			)
    UpperCAmelCase					      =  sum_aa(__A   ,       __A			)

  UpperCAmelCase					      =  reformat_hex(__A			) + reformat_hex(__A			) + reformat_hex(__A			) + reformat_hex(__A			)
  return digest


if __name__ == "__main__":
      import doctest

      doctest.testmod()






def      _lowerCAmelCase(	__A   ,       __A   ,       __A			):
  if n == 0:
    return 1

  elif n % 2 == 1:
    return (binary_exponentiation(__A   ,       n - 1   ,       __A			) * a) % mod

  else:
    UpperCAmelCase					      =  binary_exponentiation(__A   ,       n / 2   ,       __A			)
    return (b * b) % mod


# a prime number
lowerCAmelCase__       = 701

lowerCAmelCase__       = 1000000000
lowerCAmelCase__       = 10

# using binary exponentiation function, O(log(p)):
print((a / b) % p == (a * binary_exponentiation(b, p - 2, p)) % p)





print((a / b) % p == (a * b ** (p - 2)) % p)



