#include <stdio.h>
int powmod( int x, int c );
int main()
{
int number; /*做幂运算的数*/
int c; /*要用来取余的数*/
scanf("%d%d", &number, &c );
printf("%d\n", powmod( number, c ) );
return 0;
}
int powmod( int x, int c )
{
int remain; /*用来保存要输出的取余的结果*/
int a;
/*以下为快速幂算法*/
remain = 1; /*初始化*/
a = x%c; /*用来保存对c取余后的余数*/
while( x>0 ){ /*x不为0*/
if( x%2 == 1 ) /*x 为奇数的情况*/
remain = remain * a % c;
x /= 2;
a = a *a % c;
}
return remain;
}