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

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

int a,n,x;

int nrprime()
{
    int 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
    */
    x=nrprime();
    y=x-1;
    while(y!=0)
    {
        if(y%2==1)
        {
            p=p*a;
        }
        y=y/2;
        a=a*a;
    }
    out<<p%n1;
    return 0;
}