#include <bits/stdc++.h>

using namespace std;

ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

long long A,N;

long long po(long long a, long long b)
{
    if(b==0) return 1;
    if(b%2==1)
        return (a * po(a*a,b/2))%N;
    return po(a*a,b/2)%N;
}

long long phi(long long n)
{
    long long r=n,d=2;
    while(n>1)
    {
        if(n%d==0)
        {
            r = r / d * (d - 1);
            while(n%d==0)
                n/=d;
        }
        d++;
        if(d*d>n)
            d=n;
    }
    return r;
}

int main()
{
    fin>>A>>N;
    long long ph=phi(N)-1;
    fout<<po(A,ph);
    return 0;
}