


"""simple docstring"""






import dataclasses
import enum
import functools
import math
import re

# The following script is adapted from the script of TaPas.
# Original: https://github.com/google-research/tapas/master/wikisql_utils.py
from typing import Any, List, Text


SCREAMING_SNAKE_CASE__				:  Optional[Any]						= """none"""
SCREAMING_SNAKE_CASE__				:  Optional[int]						= """none"""




def        A_					(					UpperCAmelCase__       ,   UpperCAmelCase__				)     ->     Dict:
   a   :	Optional[int]						=    value.split(UpperCAmelCase__				)
   return len(UpperCAmelCase__				) > 1 and any((len(UpperCAmelCase__				) == 3 for x in split)				)




def        A_					(					UpperCAmelCase__				)     ->     Optional[int]:
   if isinstance(UpperCAmelCase__       ,   UpperCAmelCase__				):
      return value
   if isinstance(UpperCAmelCase__       ,   UpperCAmelCase__				):
      return float(UpperCAmelCase__				)
   if not isinstance(UpperCAmelCase__       ,   UpperCAmelCase__				):
      raise ValueError('Argument value is not a string. Can\'t parse it as float'				)
   a   :	Tuple						=    value

   try:
      # Example: 1,000.7
      if "." in sanitized and "," in sanitized:
         return float(sanitized.replace(','       ,   ''				)				)
      # 1,000
      if "," in sanitized and _split_thousands(','       ,   UpperCAmelCase__				):
         return float(sanitized.replace(','       ,   ''				)				)
      # 5,5556
      if "," in sanitized and sanitized.count(','				) == 1 and not _split_thousands(','       ,   UpperCAmelCase__				):
         return float(sanitized.replace(','       ,   '.'				)				)
      # 0.0.0.1
      if sanitized.count('.'				) > 1:
         return float(sanitized.replace('.'       ,   ''				)				)
      # 0,0,0,1
      if sanitized.count(','				) > 1:
         return float(sanitized.replace(','       ,   ''				)				)
      return float(UpperCAmelCase__				)
   except ValueError:
      # Avoid adding the sanitized value in the error message.
      raise ValueError('Unable to convert value to float'				)




def        A_					(					UpperCAmelCase__				)     ->     List[str]:
   if answer is None:
      return None
   try:
      a   :	List[str]						=    convert_to_float(UpperCAmelCase__				)
      if isinstance(UpperCAmelCase__       ,   UpperCAmelCase__				) and math.isnan(UpperCAmelCase__				):
         return None
      return value
   except ValueError:
      return answer.lower()


SCREAMING_SNAKE_CASE__				:  Dict						= {
    """text""": lambda x: x,
    """real""": convert_to_float,
}


class 	A_       (     enum.Enum   ):





  """simple docstring"""

  lowercase		:	int   =						0
  lowercase		:	Optional[Any]   =						1
  lowercase		:	Tuple   =						2
  lowercase		:	Optional[Any]   =						3
  lowercase		:	Dict   =						4
  lowercase		:	int   =						5



class 	A_       (     enum.Enum   ):





  """simple docstring"""

  lowercase		:	int   =						0
  lowercase		:	Dict   =						1
  lowercase		:	Optional[int]   =						2



@dataclasses.dataclass
class 	A_       :





  """simple docstring"""

  lowercase		:	Text
  lowercase		:	_Operator
  lowercase		:	Any



SCREAMING_SNAKE_CASE__				:  Dict						= re.compile(R"\w+|[^\w\s]+", re.UNICODE | re.MULTILINE | re.DOTALL)




def        A_					(					UpperCAmelCase__				)     ->     int:
   return list(_TOKENIZER.findall(x.lower()				)				)




def        A_					(					UpperCAmelCase__       ,   UpperCAmelCase__       ,   UpperCAmelCase__				)     ->     Dict:
   if operator == _Operator.EQUALS:
      return src == tgt
   elif operator == _Operator.GREATER:
      return src > tgt
   elif operator == _Operator.LESSER:
      return src < tgt
   raise ValueError(F'Unknown operator: {operator}'				)




def        A_					(					UpperCAmelCase__       ,   UpperCAmelCase__       ,   UpperCAmelCase__				)     ->     Tuple:
   a   :	str						=    table['types']
   return _TYPE_CONVERTER[types[column]](UpperCAmelCase__				)




def        A_					(					UpperCAmelCase__				)     ->     Dict:
   return isinstance(UpperCAmelCase__       ,   UpperCAmelCase__				)




def        A_					(					UpperCAmelCase__       ,   UpperCAmelCase__       ,   UpperCAmelCase__				)     ->     str:
   for cond in conditions:
      a   :	Dict						=    row[cond.column]

      a   :	List[str]						=    _parse_value(UpperCAmelCase__       ,   cond.column       ,   cond.cmp_value				)

      if _is_string(UpperCAmelCase__				) and _is_string(UpperCAmelCase__				):
         a   :	List[str]						=    _normalize_for_match(UpperCAmelCase__				)
         a   :	Tuple						=    _normalize_for_match(UpperCAmelCase__				)

      if not isinstance(UpperCAmelCase__       ,   type(UpperCAmelCase__				)				):
         raise ValueError('Type difference {} != {}'.format(type(UpperCAmelCase__				)       ,   type(UpperCAmelCase__				)				)				)

      if not _compare(cond.operator       ,   UpperCAmelCase__       ,   UpperCAmelCase__				):
         return False
   return True




def        A_					(					UpperCAmelCase__       ,   UpperCAmelCase__       ,   UpperCAmelCase__				)     ->     Optional[int]:
   if not answer_coordinates:
      if aggregation_op == _Aggregation.COUNT:
         return 0.0
      else:
         return EMPTY_ANSWER_AGG

    # Count can support non numeric answers.
   if aggregation_op == _Aggregation.COUNT:
      return float(len(UpperCAmelCase__				)				)

   # If we have just one answer, if float returns it or try a conversion.
   a   :	Dict						=    [table['rows'][i][j] for (i, j) in answer_coordinates]
   if len(UpperCAmelCase__				) == 1:
      try:
         return convert_to_float(values[0]				)
      except ValueError as e:
         if aggregation_op != _Aggregation.NONE:
            raise e

   if aggregation_op == _Aggregation.NONE:
      return None

   # Other aggregation only support numeric values. Bail out if we have strings.
   if not all((isinstance(UpperCAmelCase__       ,   (int, float)				) for v in values)				):
      return None

   if aggregation_op == _Aggregation.SUM:
      return float(sum(UpperCAmelCase__				)				)
   elif aggregation_op == _Aggregation.AVERAGE:
      return sum(UpperCAmelCase__				) / len(UpperCAmelCase__				)
   else:
      raise ValueError(F'Unknown aggregation: {aggregation_op}'				)




def        A_					(					UpperCAmelCase__       ,   UpperCAmelCase__				)     ->     Any:
   a   :	List[Any]						=    sql_query['agg']
   if aggregation_op_index >= 3:
      a   :	Any						=    _Aggregation(UpperCAmelCase__				)
   else:
      a   :	Any						=    _Aggregation.NONE

   a   :	List[Any]						=    sql_query['sel']
   a   :	Tuple						=    [
       _Condition(UpperCAmelCase__       ,   _Operator(UpperCAmelCase__				)       ,   UpperCAmelCase__				)
       for column, operator, cmp_value in zip(
           sql_query['conds']['column_index']       ,   sql_query['conds']['operator_index']       ,   sql_query['conds']['condition']				)
   ]

   a   :	Dict						=    []
   for row in range(len(table['rows']				)				):
      if _respect_conditions(UpperCAmelCase__       ,   table['rows'][row]       ,   UpperCAmelCase__				):
         indices.append((row, target_column)				)

   if not indices:
      return [], aggregation_op

   if len(UpperCAmelCase__				) == 1:
      return indices, aggregation_op

   # Parsing of MIN/MAX.
   if aggregation_op_index in (1, 2):
      a   :	Any						=    {2: min, 1: max}
      a   :	List[str]						=    [(table['rows'][i][j], index) for index, (i, j) in enumerate(UpperCAmelCase__				)]
      a   :	Dict						=    functools.reduce(operators[sql_query['agg']]       ,   UpperCAmelCase__				)

      a   :	Dict						=    [indices[reduced[1]]]
      return ret, _Aggregation.NONE

   return indices, aggregation_op




def        A_					(					UpperCAmelCase__       ,   UpperCAmelCase__       ,   UpperCAmelCase__				)     ->     Dict:
   if float_answer is not None:
      return [str(UpperCAmelCase__				)]
   return [str(table['real_rows'][r][c]				) for r, c in answer_coordinates]




def        A_					(					UpperCAmelCase__       ,   UpperCAmelCase__				)     ->     List[Any]:
   a   :	Optional[int]						=    _get_answer_coordinates(UpperCAmelCase__       ,   UpperCAmelCase__				)
   a   :	List[str]						=    _get_float_answer(UpperCAmelCase__       ,   UpperCAmelCase__       ,   UpperCAmelCase__				)
   a   :	List[Any]						=    _get_answer_text(UpperCAmelCase__       ,   UpperCAmelCase__       ,   UpperCAmelCase__				)
   # keep the original data the same with TaPas
   if len(UpperCAmelCase__				) == 0:
      a   :	List[Any]						=    [EMPTY_ANSWER]
   return answer_text










'''simple docstring'''







def  SCREAMING_SNAKE_CASE__ (				SCREAMING_SNAKE_CASE ,		SCREAMING_SNAKE_CASE ,		SCREAMING_SNAKE_CASE     ):
		assert b != 0, "This cannot accept modulo that is == 0"
		if n == 0:
				return 1

		if n % 2 == 1:
				return (bin_exp_mod(SCREAMING_SNAKE_CASE ,		n - 1 ,		SCREAMING_SNAKE_CASE     ) * a) % b

		SCREAMING_SNAKE_CASE_						:List[str]										=      bin_exp_mod(SCREAMING_SNAKE_CASE ,		n / 2 ,		SCREAMING_SNAKE_CASE     )
		return (r * r) % b


if __name__ == "__main__":
							try:
														SCREAMING_SNAKE_CASE__     : Any				=   int(input("""Enter Base : """).strip())
														SCREAMING_SNAKE_CASE__     : str				=   int(input("""Enter Power : """).strip())
														SCREAMING_SNAKE_CASE__     : List[Any]				=   int(input("""Enter Modulo : """).strip())
							except ValueError:
														print("""Invalid literal for integer""")

							print(bin_exp_mod(BASE, POWER, MODULO))
