#include <fstream>

using namespace std;

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

int a,n;
int euler(int n)
{
    int prod=n;
    for(int d=2;d*d<=n;d++)
    {
        if(n%d==0)
        {
            prod=prod*(d-1)/d;
            while(n%d==0)
                n/=d;
        }
    }
    if(n!=1)
        prod=prod*(n-1)/n;
    return prod;
}
int putere(int a, int p)
{
    if(p==0)
        return 1;
    else
    {
        int aux=putere(a,p/2)%n;
        aux=1LL*aux*aux%n;
        if(p%2!=0)
            aux=1LL*aux*a%n;
        return aux;
    }
}
int main()
{
    fin>>a>>n;
    int k=euler(n);
    ///(a^(k-1))%n-inversul modular cautat
    fout<<putere(a,k-1);
    return 0;
}