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

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

long long a,n,x;

bool prim()
{
    int d=2;
    while(d*d<n)
    {
        if(n%d==0)
            return false;
        d++;
    }
    if(d*d==n)
        return false;
    return true;
}
int nrprime()
{
    long long d=2,p,nr=n;
    while(n>1)
    {
        p=0;
        while(n%d==0)
        {
            p++;
            n=n/d;

        }
        if(p!=0)
        {
            nr=nr*(d-1)/d;
        }
        d++;
    }
    return nr;
}
int main()
{
    in>>a>>n;
    long long y,p=1,n1=n;
    /*
    fi(n) = cate numere naturale mai mici ca n sunt prime cu n (indicatorul lui Euler)
    a^fi(n) = 1 modulo n
    => a^(fi(n)-1) = inversul lui modulo n
    daca n = d1^p1 * d2^p2 * ... *dk^pk, atunci fi(n) = n * (d1-1)/d1 * (d2-1)/d2 * ... * (dk-1)/dk
    */
    if(prim()==0)
        x=nrprime();
    else
        x=n-1;
    x=x-1;
    while(x!=0)
    {
        if(x%2==1)
        {
            p=p*a;
        }
        x=x/2;
        a=a*a;
    }
    out<<p%n1;
    return 0;
}