#include <fstream>

using namespace std;
int a,n;

int Fi(int n)
{
    int d, fi;
    d=2;
    fi=n;
    while (n>1&&d*d<=n)
    {
        if (n%d==0)
        {
            fi=(fi/d)*(d-1);
            while (n%d==0)
                n=n/d;
        }
        d++;
    }
    if (n>1) fi=(fi/n)*(n-1);
    return fi;
}

int Putere(int a, int k)
{   int prod;
    prod=1;
    while (k>0)
    {
        if (k%2==1)
        {
            k--;
            prod=1LL*prod*a%n;
        }
        k=k/2;
        a=1LL*a*a%n;
    }
    return prod;
}

int main()
{
    ifstream fin ("inversmodular.in");
    ofstream fout ("inversmodular.out");
    int k;

    fin >> a >> n;
    k=Fi(n)-1;
    fout << Putere(a,k) << "\n";
    fin.close();
    fout.close();
    return 0;
}