#include <bits/stdc++.h>

using namespace std;

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

int A,N;

int po(int a, int 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;
}

int phi(int n)
{
    int 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;
    int ph=phi(N)-1;
    fout<<po(A,ph);
    return 0;
}