#include <fstream>
#include <vector>
#include <cmath>
using namespace std;

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

int v[1000000];

bool isPrime(int n)
{
    for(int i = 2; i<=sqrt(n); i++)
        if(n%i==0)
            return false;
    return true;
}

int power(int baza, int exp)
{
    int rez = 1;
    while(exp!=0)
    {
        if(exp%2==0)
        {
            baza = baza * baza;
            exp/=2;
        }
        else
        {
            rez = rez * baza;
            exp--;
        }
    }
    return rez;
}

int main()
{
    int n, a;
    in>>a>>n;
    if(isPrime(n))
        out<<power(a, n-2) % n;
    else
    {
        int d = 2, x, nrf = 0, cn = n, ok;
        while(cn!=1)
        {
            ok = 0;
            while(n%d==0)
            {
                n/=d;
                ok = 1;
            }
            if(ok)
                v[++nrf]=d;
        }
        int phi = n;
        for(int i = 1; i<=nrf; i++)
            phi*=(1-1/v[i]);
        out<<power(a, phi-1) % n;
    }
    return 0;
}