#include <fstream>

using namespace std;
typedef long long ll;

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

int phi(int n)
{
    int i,curr = n;
	for(i = 2; i * i <= n; i++)
		if (n % i == 0)
		{
			while(n % i == 0)
                n = n / i;
			curr = (curr / i) * (i - 1);
		}
    if(n != 1)
        curr = curr / n * (n - 1);
	return curr;
}

ll lgput(int x, int y, int MOD)
{
    ll ans = 1;
    int i;
    for(i = 1; i <= y; i <<= 1)
    {
        if(i & y)
            ans = (1LL * ans * x) % MOD;
        x = (x * x) % MOD;
    }
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(NULL);

    int n,a,x;
    fin >> a >> n;
    x = phi(n) - 2;
    fout << lgput(a,x,n);
    return 0;
}