#!/bin/bash

if [ $# -ne 3 ]; then
	echo "Usage: $0 BASE EXPONENT MODULE"
	exit 1
fi

BASE=$1
EXP=$2
MOD=$3

if [ "$EXP" == "0" ]; then
	echo "1"
	exit
fi

TEMP=$BASE

BITS=`echo "obase=2; $EXP" | bc`
NUM=`echo -n $BITS | wc -c`

for i in `seq 2 $NUM`; do
	TEMP=`echo "($TEMP * $TEMP)" | bc`
	BIT=`echo $BITS | cut -c$i`
	if [ "$BIT" == "1" ]; then
		TEMP=`echo "$TEMP * $BASE" | bc`
	fi
	TEMP=`echo "$TEMP % $MOD" | bc`
done

echo $TEMP