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

ll a, n, x;

ll gcd(ll a, ll b)
{
    if (b == 0) return a;
    else return gcd(b, a % b);
}

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 (int) phi;
}

bool ciurCalc(ll n)
{
    bool ciur[n + 10];
    for (ll i = 0; i < n + 10; i++)
    {
        ciur[i] = 1;
    }
    ciur[0] = ciur[1] = 0;
    for (ll i = 2; i < n + 10; i++)
    {
        if (ciur[i] == 1) for (ll j = 2 * i; j < n + 10; j += i) ciur[j] = 0;
    }
    return ciur[n];
}

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;

if (ciurCalc(n))
{
    cout << expon(a, n - 2) % n << "\n";
    return 0;
}
else
{
    cout << expon(a, phiCalc(n) - 1) % n << "\n";
}

return 0;
}