/*#include <bits/stdc++.h>
typedef unsigned long long ul;
typedef long long ll;
using namespace std;

ll a, n, x;

ll phiCalc(ll n)
{
    float phi = n;
    for (ll p = 2; p * p <= n; p++)
    {
        if (n % p == 0)
        {
            while (n % p == 0) n /= p;
            phi *= (1.0 - (1.0 / (float)p));

        }
    }
    if (n > 1) phi *= (1.0 - (1.0 / (float)n));
    return (ll) phi;
}

ll expon(ll b, ll p)
{
    if (p == 0) return 1;
    else if (p == 1) return b % n;
    else if (p % 2 == 0) return expon((b%n * b%n) % n, p / 2) % n;
    else if (p % 2 == 1) return (b % n) * (expon((b%n * b%n) % n, (p - 1) / 2) % n);
}

int main(){
ios_base::sync_with_stdio(0); cin.tie(); cout.tie();
//ifstream cin("inversmodular.in");
//ofstream cout("inversmodular.out");

cin >> a >> n;

cout << expon(a, phiCalc(n) - 1) % n << "\n";


return 0;
}*/

#include<stdio.h>
#define LL long long


LL N,M;

LL getphi(LL nr)
{
	LL cur = nr;
	for(LL i = 2;i * i <= nr; ++i)
	{
		if (nr % i == 0)
		{
			while(nr % i == 0)nr /= i;
			cur = (cur / i) * (i - 1);
		}
	}
        if (nr != 1) cur = cur / nr * (nr - 1);
	return cur;
}

int main()
{
	freopen("inversmodular.in","r",stdin);
	freopen("inversmodular.out","w",stdout);
	scanf("%lld %lld\n",&N,&M);
        LL put = getphi(M) - 1;
	LL nr = N;
	LL crt = 1;
    for(LL p = 1;p <= put;p <<= 1)
    {
	 	if (p & put) crt = (crt * nr) % M;
	  	nr = (nr * nr) % M;
	}
	printf("%lld\n",crt);
	return 0;
}