

from __future__ import annotations



def    snake_case_(_UpperCamelCase				, _UpperCamelCase				, _UpperCamelCase  )							->			int:



  """simple docstring"""






  assert n > 1 and a > 0 and greatest_common_divisor(_UpperCamelCase				, _UpperCamelCase  ) == 1
  ((_snake_case),  (_snake_case),  (_snake_case))		=      extended_gcd(_UpperCamelCase				, _UpperCamelCase  )  # Implemented below
  _snake_case		=      (b * s) % n
  return x



def    snake_case_(_UpperCamelCase				, _UpperCamelCase  )							->			int:



  """simple docstring"""






  ((_snake_case),  (_snake_case))		=      extended_euclid(_UpperCamelCase				, _UpperCamelCase  )  # Implemented below
  if b < 0:
    _snake_case		=      (b % n + n) % n
  return b



def    snake_case_(_UpperCamelCase				, _UpperCamelCase				, _UpperCamelCase  )							->			int:



  """simple docstring"""






  _snake_case		=      invert_modulo(_UpperCamelCase				, _UpperCamelCase  )
  _snake_case		=      (b * s) % n
  return x



def    snake_case_(_UpperCamelCase				, _UpperCamelCase  )							->			tuple[int, int, int]:



  """simple docstring"""






  assert a >= 0 and b >= 0

  if b == 0:
    _snake_case,  _snake_case,  _snake_case		=      a, 1, 0
  else:
    ((_snake_case),  (_snake_case),  (_snake_case))		=      extended_gcd(_UpperCamelCase				, a % b  )
    _snake_case		=      q
    _snake_case		=      p - q * (a // b)

  assert a % d == 0 and b % d == 0
  assert d == a * x + b * y

  return (d, x, y)



def    snake_case_(_UpperCamelCase				, _UpperCamelCase  )							->			tuple[int, int]:



  """simple docstring"""






  if b == 0:
    return (1, 0)
  ((_snake_case),  (_snake_case))		=      extended_euclid(_UpperCamelCase				, a % b  )
  _snake_case		=      a // b
  return (y, x - k * y)



def    snake_case_(_UpperCamelCase				, _UpperCamelCase  )							->			int:



  """simple docstring"""






  if a < b:
    _snake_case,  _snake_case		=      b, a

  while a % b != 0:
    _snake_case,  _snake_case		=      b, a % b

  return b


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

 testmod(name='''modular_division''', verbose=True)
 testmod(name='''modular_division2''', verbose=True)
 testmod(name='''invert_modulo''', verbose=True)
 testmod(name='''extended_gcd''', verbose=True)
 testmod(name='''extended_euclid''', verbose=True)
 testmod(name='''greatest_common_divisor''', verbose=True)




__A    	=			{
    '''+''': lambda x, y: x + y,
    '''-''': lambda x, y: x - y,
    '''*''': lambda x, y: x * y,
    '''/''': lambda x, y: x / y,
}



def    snake_case_(_UpperCamelCase  )							->			str:



  """simple docstring"""






  return c.isdigit()



def    snake_case_(_UpperCamelCase  )							->			str:



  """simple docstring"""






  _snake_case		=							[]

  # iterate over the string in reverse order
  for c in expression.split()[::-1]:
    # push operand to stack
    if is_operand(_UpperCamelCase  ):
      stack.append(int(_UpperCamelCase  )  )

    else:
      # pop values from stack can calculate the result
      # push the result onto the stack again
      _snake_case		=							stack.pop()
      _snake_case		=							stack.pop()
      stack.append(calc[c](_UpperCamelCase				, _UpperCamelCase  )  )

  return stack.pop()


# Driver code
if __name__ == "__main__":
 __A    	=			'''+ 9 * 2 6'''
 print(evaluate(test_expression))

 __A    	=			'''/ * 10 2 + 4 1 '''
 print(evaluate(test_expression))

