#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <algorithm>
#include <utility>
#include <string>
#include <functional>
#include <sstream>
#include <fstream>
#include <iostream>
using namespace std;
#define FOR(i,a,b) for (i=a;i<=b;i++)
#define fori(it,v) for (it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define mp make_pair
#define fs first
#define ss second
#define all(c) c.begin(),c.end()
#define pf push_front
#define popb pop_back
#define popf pop_front
FILE *in,*out;
long long euler(long long n)
{
	long long i;
	long long rez=n;
	for(i=2;(i*i)<=n;i++)
		if (n%i==0)
		{
			rez=rez/i*(i-1);
			while (n%i==0)
				n/=i;
		}
	if (n!=1)
	{
		rez=rez/n*(n-1);
	}
	return rez;
}
int main()
{
	long long n,A,x,i,rez=1;;
	in=fopen("inversmodular.in","r");
	out=fopen("inversmodular.out","w");
	fscanf(in,"%lld%lld\n",&A,&n);
	x=euler(n);
	x--;
	for(i=1;i<=x;i<<=1)
	{
		if (x&i)
			rez=(rez*A)%n;
		A=(A*A)%n;
	}
	fprintf(out,"%lld\n",rez);
	fclose(in);
	fclose(out);
	return 0;
}