#include <stdio.h>
#include <math.h>
#include <iostream>
#include <string>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <queue>
#include<cstdlib>
using namespace std;
	
#define MAXN 101
//#define MOD 1999999973
#define INF 1<<30

int v[MAXN];
int MOD;
long long int expbysquaring(long long int x, long long int n)
{
	if ( n < 0 )
		return (expbysquaring(1/x , -n) % MOD);
     else if ( n == 0 )
		 return 1;
     else 
		 if ( n == 1 )
			 return x % MOD;
     else
		 if ( n % 2 == 0 ) 
			 return (expbysquaring((x * x) % MOD, n/2)) % MOD;
     else
		 if ( n % 2 > 0 )
			return ( x * expbysquaring((x * x) % MOD, (n-1)/2)) % MOD;

}

int isPrime (int x)
{
	int rad = sqrt(x);
	for (int i = 2; i <= rad; i++)
	{
		if ( x % i == 0 )
			return 0;
	}
	return 1;
}
int cmmdc(int a, int b)
{
	while (b != 0)
	{
		int r = a % b;
		a = b; 
		b = r;
	}
	return a;
}
int main()
{
	FILE *f = fopen("inversmodular.in", "r");
	FILE *g = fopen("inversmodular.out", "w");

	long long int A, N;
	fscanf(f, "%lld %lld", &A, &N); 
	MOD = N;

	if ( isPrime(N) == true )
	{
		fprintf(g, "%lld", (expbysquaring(A, N-2)) % MOD);
	}
	else
	{
		int copie_N = N, nr = 1;
		for (int i = 2; i < N; i ++)
		{
			if ( cmmdc(i, N) == 1 )
				nr++;
		}
		fprintf(g, "%lld", (expbysquaring(A, nr-1)) % MOD);
	}
	fclose(f); fclose(g);
	return 0;
}