#include <iostream>

using namespace std;
int a,n;
int Phi(int N)
{
    int rez=N,d=2;
    while(N>1)
    {
        if(N%d==0)
        {
            rez=rez/d*(d-1);
            while(N%d==0)N/=d;
        }
        d++;
        if(d*d>N)break;
    }
    return rez;
}
int Power(int a, int b, int n)
{
    int p=1;
    while(b)
    {
        if (b%2==1)
        {
            p*=a;
            p%=n;
        }
        a*=a;
        a%=n;
        b/=2;
    }
    return p;
}
int main()
{
    cin>>a>>n;
    cout<<Power(a,(Phi(n)-1),n);
    return 0;
}