#include <fstream>
#include <iostream>
#include <cstring>

using namespace std;

#define MAX 100005

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

long long n,a,x,tot,aa,d=2,k,i,sol=1;

int main()
{
    ios_base::sync_with_stdio(false);
    fin >> a >> n;
    aa=n;
    tot=n;
    while(d*d<=aa)
    {
        if(aa%d==0)
        {
            while(aa%d==0)
                aa/=d;
            tot/=d;
            tot*=d-1;
        }
        d++;
    }
    if(aa>1)
        tot/=aa,
        tot*=aa-1;
    tot--;
    for (i=0;(1<<i)<=tot;++i)
	{
		if (((1<<i)&tot)>0)
			sol=((sol%n)*(a%n))%n;
			a=(a%n)*(a%n))%n;
	}
	fout << sol;
    return 0;
}