#include <fstream>

using namespace std;
ifstream cin("inversmodular.in");
ofstream cout("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/=d;
            prod*=(d-1);
            while(n%d==0)
                n=n/d;
        }
    }
    if(n!=1)
    {
        prod/=n;
        prod=prod*(n-1);
    }
    return prod;
}
int putere( int b)
{
    if(b==0)
        return 1;
    else
    {
        int aux=putere(b/2)%n;
        aux=1LL*aux*aux%n;
        if(b%2!=0)
            aux=1LL*aux*a%n;
        return aux;
    }
}
int main()
{
    cin>>a>>n;
    int k=euler(n);
    ///(a la puterea k-1 )%n -inversul modular cautat
    cout<<putere(k-1);
    return 0;
}