/************************************************
Grundlegende Algorithmen mit Java,
http://algorithmen-und-problemloesungen.de/
Copyright @2007-2008 by Doina Logofatu

in C#: Michael Gärtner
************************************************/


using System;
using System.IO;

namespace Logofatu
{
    class P03BigMod
    {
        private static String FileInputName = "bigmod.in";
        private static String FileOutputName = "bigmod.out";

        private static long bigMod(long b, long p, long m)
        {
            if ( 0 == p )
            {
                return 1;
            }
            if ( 0 == b )
            {
                return 0;
            }
            if ( 1 == b || 1 == p )
            {
                return b % m;
            }
            if ( 1 == m )
            {
                return 0;
            }
            if ( 0 == p % 2 )
            {
                long aux;
                aux = bigMod(b, p / 2, m);
                return (aux * aux) % m;
            }
            else
                return (bigMod(b, p - 1, m) * (b % m)) % m;
        }

        static void Main(string[] args)
        {
            StreamReader sr = null;
            StreamWriter sw = null;
            try
            {
                sr = new StreamReader(FileInputName);
                sw = new StreamWriter(FileOutputName);
                while ( !sr.EndOfStream )
                {
                    string[] sArray = sr.ReadLine().Split(' ');
                    long b = long.Parse(sArray[0]);
                    long p = long.Parse(sArray[1]);
                    long m = long.Parse(sArray[2]);
                    sw.WriteLine(bigMod(b, p, m));
                }

            }
            catch ( IOException ex )
            {
                Console.WriteLine("Fehler bei der Dateiverarbeitung!\n" + ex); 
            }
            finally
            {
                if ( sr != null )
                {
                    sr.Close();
                }
                if ( sw != null )
                {
                    sw.Close();
                }
            }
        }
    }
}