#include <bits/stdc++.h>
#define ll long long

using namespace std;

ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

ll a, n;

int phi(int x)
{
    int k = x;
    if(x % 2 == 0)
        k /= 2;
    while(x % 2 == 0)
        x /= 2;

    int d = 3;
    while(x > 1)
    {
        if(x % d == 0)
        {
            k = k / d * (d - 1);
            while(x % d == 0)
                x /= d;
        }
        d += 2;
        if(d * d > x)
            d = x;
    }

    return k;
}

ll powerLog(int a, int b)
{
    ll rez = 1;
    while(b)
    {
        if(b % 2 == 1)
            rez = 1LL * a * rez % n;
        a = 1LL * a * a % n;
        b /= 2;
    }

    return rez;
}

ll inversModular(int a, int n)
{
    return powerLog(a, phi(n) - 1);
}

int main()
{
    f >> a >> n;
    g << inversModular(a, n);
    return 0;
}