#include<math.h>
#include<stdio.h>
//#include"momi.h"
void main()
{ int momi(int,int,int);
  int a,b,c,d;
  printf("x^r(modp),Enter your number:\n");
  printf("x=");
  scanf("%d",&a);
  printf("r=");
  scanf("%d",&b);
  printf("p=");
  scanf("%d",&c);
  d=momi(a,b,c);
  printf("%d^%d(mod%d)=%d\n",a,b,c,d);
}

int momi(int a,int b,int p)
{ 
  int d,c=1;
  if(a==0) return 0;
  while(b!=0)
  {  d=b%2;
     while(d==0)
     {  b=b/2;
        a=(a*a)%p;
        d=b%2;
     }
  b=b-1;
  c=(a*c)%p;
  }
  return(c);
}