//invers modular O(log(n))+O(sqrt(n)) folosind indicatorul lui euler si teorema lui fermat
#include <fstream>
#include <cstdio>
#include <cmath>
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
int n;


long long exponentiere(int a, int b)
{
    if (b==0)
        return 1;
    if (b%2==0)
        return 1LL*exponentiere((1LL*a*a)%n,b/2);
    if (b%2==1)
        return 1LL*(exponentiere((1LL*a*a)%n,b/2)*a)%n;

}
int fii(int k)
{
    int p[10]={0},e[10]={0},t=0;
    double sol=k;
    int i=2;
    while (k-1) {
        if (k%i==0) {
            p[++t]=i;
            e[t]=1;
            while (k%i==0) {
                k/=i;
                e[t]++;
            }
        }
        else
            if (i*i>k) {
                p[++t]=k;
                e[t]=1;
                k=1;
            }
        i++;
    }

    for (i=1;i<=t;i++)
        sol=sol*double((1.0-1.0/p[i]));
    return int(round(double(sol)));
}

int main()
{
    int a;
    f>>a>>n;
    g<<exponentiere(a,fii(n)-1);

    return 0;
}