#include <fstream>
using namespace std;
ifstream   in("inversmodular.in");
ofstream out("inversmodular.out");
int main()
{
    bool ok;
    unsigned long long i , n , r , a , ca=a , p;
    in>>a>>n;
    p=n;
    while (p)
    {
        if (p/2)
        {
            ca=(ca*ca)%n;
            ok=p%2;
            p/=2;
            p+=ok;
        }
        if (p==1)
        while (p)
        {
            ca=(ca*a)%n;
            p--;
        }

    }
    out<<ca;
    return 0;
}