import java.io.*;

public class GetRemainder
{     
      
      static long result;
      
       
      public static void main(String args[])
      {
      	
      String input="";
      long dishu,zhishu,model;
      
      try{
           BufferedReader in=new BufferedReader(
              new InputStreamReader(System.in) );	
           System.out.println("請輸入底數(shù)：");
           input=in.readLine();
           dishu=Integer.parseInt(input);
           
           System.out.println("請輸入指數(shù)：");
           input=in.readLine();
           zhishu=Integer.parseInt(input);
           
           
           System.out.println("請輸入模：");
           input=in.readLine();
           model=Integer.parseInt(input);
           
           result=get_remainder(dishu,zhishu,model);
           System.out.println();
           System.out.println(dishu+" 的 "+zhishu+" 次方對 "+model+" 求余所得的結(jié)果為: "+result);
           
         }catch (IOException e){System.out.println(e);}
         
      }	
      
      
      public static long  get_remainder(long dishu,long zhishu,long model)
      {    
           System.out.println("運(yùn)算過程如下：");
           result=1;
           String string_zhishu="";
           Long long_zhishu=new Long(zhishu);
           string_zhishu=long_zhishu.toBinaryString(zhishu);
           int length=string_zhishu.length();
           for(int i=0;i<length;i++)
           {
           	    if(string_zhishu.charAt(i)=='1')
           	        {
           	         System.out.print("1:  ( "+result+" * "+result+" )* "+dishu+" mod( "+model+" )= ");	
           	         result=(result*result*dishu)%model;
           	         System.out.println(result);
           	        // System.out.println();
           	        }
           	    else 
           	        {
           	         System.out.print("0:  ( "+result+" * "+result+" ) "+" mod "+model+" = ");
           	         result=(result*result)%model;  
           	         System.out.println(result);
           	         //System.out.println();
           	        }  
           }
           
      	   return result;
      }
}