#include <fstream>
#include <iostream>
#define int long long

using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

int a,n;


int phi(int n)
{
    int aux=n,p,d=2;
    while (d*d<=n)
    {
        p=0;
        while (n%d==0)
        {n/=d; p++;}

        if (p!=0)
            aux=aux/d*(d-1);


        d++;
    }

    if (n>1)
        aux=aux/n*(n-1);

    return aux;
}

int putere(int a, int p)
{
    if (p==0)
        return 1;
    if (p%2==1)
        return a*putere(a,p-1)%n;
    int P=putere(a,p/2)%n;
    return P*P%n;
}

signed main()
{
    fin>>a>>n;
    fout<<putere(a,phi(n)-1);
    return 0;
}