#include <fstream>

using namespace std;
ifstream in ("inversmodular.in");
ofstream out ("inversmodular.out");
bool cmmmdc(int a , int b)
{   int x;
    while(a!=b)
    {
        if(a>=b)
            a=a-b;
        else
            b=b-a;
    }
    x=b;
    if(x==1)
        return 1;
    else
        return 0;
}
int main()
{int a,x=1,n,i,ct=0;
in>>a>>n;
for(i=1;i<n;i++)
{
    if(cmmmdc(i,n)==1)
        ct++;
}
for(i=1;i<=ct-1;i++)
{
    x=x*a;
}
out<<x%n;
    return 0;
}