#include<fstream>
using namespace std;
#define ll long long

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

ll getFi(ll a) {
	ll curr = a;
	ll i = 2;

	for (; i * i <= a; i++) {
		if (a % i == 0) {
			while (a % i == 0) { a /= i; }
			curr = (curr / i) * (i - 1);
		}
	}
	if (a != 1) {
		curr = (curr / a) * (a - 1);
	}
	return curr;
}


ll pow(ll n, ll m,ll mod) {
    if (m == 0) {
        return 1;
    } else {
        if (m == 1) {
            return n;
        }
        else {
            ll pw = pow(n, m / 2, mod);
            if (m % 2 == 0) {
                return (ll)(pw * pw)% mod;
            }
            else {
                return (ll)(n * (pw * pw)% mod)% mod;
            }
        }
    }
	/*ll res = 1;
	while (m > 0) {
        if (m % 2) {
            res = (res * n) % mod;
            m--;
        } else {
            n = (n * n) % mod;
            m /= 2;
        }
       // m /= 2;
	}
	return res;*/
}

int main() {

	ll i,a,m,res;

	cin >> a >> m;

	ll fi = getFi(m)-1;
	//cout << pow(3, 5, 1251351);

	//i = 1;
	cout << pow(a, fi, m)%m;

	return 0;
}