#include <iostream>
#include <fstream>
using namespace std;

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

long long n;

long long inversmodular(long long a, long long n){
    for(long long i=1;i<=n-1;i++){
        if(a*i%n==1) return i;
    }
    return -1;
}

long long Phi(long long n){
    long long d=2, nr=n;
    while(n>1){
        if(n%d==0){
            nr=nr/d*(d-1);
            while(n%d==0){
                n/=d;
            }

        }
        if(d==2) d++;
        else d+=2;
        if(d*d>n) d=n;
    }
    return nr;
}

long long Putere(long long A , long long p)
{
    long long P = 1;
    while(p)
    {
        if(p % 2 == 1)
            P = P * (A%n)%n;
        A = (A%n) * (A%n)%n;
        p /= 2;
    }
    return P;
}

int main()
{
    long long a, phin, prod;
    f>>a>>n;
    phin=Phi(n);
    g<<Putere(a,phin-1)%n;
    return 0;
}