#include <iostream>
#include <fstream>
#define nmax 200000
using namespace std;

//int euler[nmax + 2];
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
/*void ciur_euler(int n)
{
    int i, j;
    for(i = 2; i<=n; i++)
        euler[i] = i;
    for(i = 2; i<=n; i++)
    {
        if(euler[i] == i)
        {
            for(j = i; j<=n; j = j + i)
                euler[j] = euler[j] * (i-1)/i;
        }
    }
}
*/
long long euler_s(long long n)
{
    long long nr = 1, i, j;
    for(i = 2; i<=n; i++)
    {
        bool ok = 1;
        for(j = 2; j<=i; j++)
        {
            if(i % j == 0 && n % j == 0)
            {
                ok = 0;
                break;
            }
        }
        if(ok == 1)
        {
            //cout<<i<<" "<<nr<<endl;
            nr++;
        }
    }
    return nr;
}
unsigned long long fast_exp(unsigned long long a, unsigned long long b)
{
    unsigned long long aa = a, p;
    for(p = 1; b; b>>=1)//impart b mereu la 2
    {
        if(b & 1)// daca e impar
            p *= aa;
        aa *= aa;
    }
    return p;
}

unsigned long long invers_modular(unsigned long long a, unsigned long long n)
{
    return fast_exp(a, euler_s(n)-1)%n;
    //return fast_exp(a, n-2);
}
int main()
{
    unsigned long long i, n, a;
    fin>>a>>n;
    //ciur_euler(n);
      //  cout<<endl;
    fout<<invers_modular(a, n);
    return 0;
}