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

long long indeuler(long long n)
{
    long long i, e;
    e = n;
    for (i=2; i*i<=n; i++)
        if(n%i==0)
        {
            e=n*(i-1)/i;
            while (n % i == 0)
                n /= i;
        }
    if (n != 1)
        e = e / n * (n - 1);
    return e;
}

long long akmodn(long long a, long long k, long long n)
{
    long long p=1;
    while(k!=0)
    {
        if(k%2!=0)
            p=p*a%n;
        k /= 2;
        a=a*a%n;
    }
    return p;
}

int main()
{
    long long l, d, n, a, e;
    ifstream in("inversmodular.in");
    ofstream out("inversmodular.out");
    in>>a>>n;
    e=indeuler(n);
    out<<akmodn(a, e-1, n);
    return 0;
}