#include <iostream>
#include <fstream>
using namespace std;
int c;
int euler(int n)
{

	int d=2,phi=n,e=0;
	while(d*d<=n and n>1)
	{
		while(n%d==0)
		{
			e++;
			n/=d;
		}
		if(e>0)
		  phi=phi/d*(d-1);
		  e=0;
		  d++;
	}
	if(n>1)
	phi=phi/n*(n-1);
	return phi;
}
int modulo(int a, int b) {
  if (b == 0)
    return 1;
  else {
    long long x = modulo(a, b / 2);
    if (b % 2 == 0)
      return x * x % c;
    else
      return x * x % c * a % c;
  }
}

int main()
{
    ifstream cin ("inversmodular.in");
    ofstream cout ("inversmodular.out");

    int a,phi;
    cin>>a>>c;
    phi=euler(c)-1;
    cout<<modulo(a,phi);
    return 0;
}