#include <fstream>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
int a,n;
long long int putere(int,int);
int Phi(int);
int main()
{
    fin>>a>>n;
    fout<<putere(a,Phi(a)-1)<<'\n';
    return 0;
}

int Phi(int b)
{int d,rez;
 for(d=2,rez=1; d*d<=b; d++)
     if(b%d==0)
        {while(b%d==0)
            {b/=d;
             rez*=d;
            }
        rez/=d;
        rez*=(d-1);
        }
 if(b>1) rez*=(n-1);
 return rez;
}

long long int putere(int x,int b)
{
 long long int p;
 if(b==0) return 1;
 if(b%2==1) return (x*putere(x,b-1))%n;
 p=(putere(x,b/2))%n;
 return (p*p)%n;
}