#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_termen(long long n)
{
    long long nr = n, i;
    for(i = 2; i*i<=n; i++)
    {
            if(n % i == 0)
            {
                while(n % i == 0)
                    nr = nr/i;
                nr = nr/i *(i-1);
            }
    }
    if(n !=1 )
        nr = nr /n *(n-1);
    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_termen(n)-1)%n;
    //return fast_exp(a, n-2);
}
int main()
{
    unsigned long long  n, a;
    fin>>a>>n;
    //ciur_euler(n);
      //  cout<<endl;
    fout<<invers_modular(a, n);
    return 0;
}