#include <iostream.h>
void main()
{ 
	int c;
	int l,m,n;
	int x,r,p;
	int cc[10000];
	cout<<"x=";
	cin>>x;
	cout<<"r=";
	cin>>r;
	cout<<"p=";
	cin>>p;
	l=r;
	c=1;
	n=0;
  /*---------將指數轉換為2進制數-------*/
    while(l!=0)
		{
			m=l%2;
			if(m==0)
			{
				cc[n]=0;
				n++;
			}
			else
			{
				cc[n]=1;
				n++;
			}
            l=l/2;
		}
  /*-------快速指數模算法-------*/
	 n=n-1;
     while(n>=0)
     {
         c=(c*c)%p;
         if(cc[n]==1)
         {
             c=(c*x)%p;
         }
       n--;
     }
     cout<<endl;       
     cout<<"x"<<"的"<<"r"<<"次方模"<<"p"<<"的結果是"<<c<<endl;
}