#include <iostream>
#include <fstream>
#define nmax 2000000
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;
        }
    }
}
int fast_exp(int a, int b)
{
    int 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;
}

long long invers_modular(int a, int n)
{
    return fast_exp(a, euler[n]-1)%n;
}
int main()
{
    int i, n, a;
    fin>>a>>n;
    ciur_euler(n);
    //for(i = 1; i<=n; i++)
        //cout<<euler[i]<<" ";
       // cout<<endl;
    fout<<invers_modular(a, n);
    return 0;
}