#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

int a,n,i;
long long p,y;

int nr_prim(int x)
{
    int i,nrd,m;
    nrd=0;
    m=sqrt(x);
    for(i=2;i<=m;i++)
    {
        if(x%i==0) nrd=nrd+2;
    }
    if(nrd==0) return 1;
    else return 0;
}

int main()
{
    fin>>a>>n;
    p=a;
    if(nr_prim(n)==1)
    {
        for(i=1;i<=n-2;i++)
        {
            p=p*a;
        }
        while((p/n)>n)
        {
            y=p%n;
            p=p/n;
        }
        fout<<y;
    }
    else
    {

    }
    fin.close();
    fout.close();
    return 0;
}