#include<fstream>

using namespace std;

ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

long long a, n, fi;

long long functia_lui_Euler(int n)
{
    long long aux=n, p=2, rez=n;

    while (p*p<=n)
    {
        if (aux%p==0)
        {
            rez/=p;
            rez*=p-1;
        }

        while (aux%p==0) aux/=p;

        ++p;
    }

    if (aux!=1)
    {
        rez/=aux;
        rez*=aux-1;
    }

    return rez;
}

long long ridica(int x)
{
    long long z1, z2;

    if (x==0) return 1;

    if (x%2==1)
    {
        z1=a;

        z2=ridica(x-1);

        z1=(z1*z2)%n;

        return z1;
    }
    else
    {
        z2=z1=ridica(x/2);

        z1=(z1*z2)%n;

        return z1;
    }
}

int main()
{
    f>>a>>n;

    fi=functia_lui_Euler(n);

    g<<ridica(fi-1)<<"\n";

    f.close();
    g.close();
    return 0;
}