#include <iostream>
#include <fstream>
using namespace std;
ifstream in("inversmodular.in");
ofstream out("inversmodular.out");
bool prim(int x)
{
    if(x==0 || x==1) return 0;
    for(int i=2;i*i<=x;i++) if(x%i==0) return 0;
    return 1;
}
int phi(int n)
{
    if(prim(n)) return n-1;
    int baza=3;
    long long rez=n;
    if(n%2==0)
    {
        rez/=2;
        while(n%2==0) n/=2;
    }
    while(n!=1)
    {
        /*if(prim(n))
        {
            rez*=n-1;
            rez/=n;
            break;
        }*/
        if(n%baza==0 && prim(baza))
        {
            rez*=baza-1;
            rez/=baza;
            while(n%baza==0) n/=baza;
        }
        baza+=2;
    }
    return rez;
}
int main()
{
    int cop;
    long long unsigned a,n,p=1;
    in>>a>>n;
    cop=n;
    n=phi(n)-1;
    while(n)
    {
        if(n%2)
        {
            p*=a;
            if(p>cop) p%=cop;
        }
        n/=2;
        a*=a;
        if(a>cop) a%=cop;
    }
    out<<p;
    return 0;
}