#include <bits/stdc++.h>

using namespace std;

vector <int> nr_prime;

long long MOD;
long long phi_n;
void descomp_prim(long long n)
{
    phi_n=n;
    for(int i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            nr_prime.push_back(i);
            while(n%i==0)
                n/=i;
            phi_n=(phi_n/i)*(i-1);
        }
    }
    if(phi_n==n)
        phi_n--;
}
long long multy(long long& a, long long b)
{
    a=int64_t(a)*b%MOD;
}
long long exp_by_squaring(long long a, long long b)
{
    long long ans = 1;
    while (b > 0)
    {
        if (b&1)
            multy(ans, a);
        b>>=1;
        multy(a, a);
    }
    return ans;
}
int main()
{
    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);
    long long a, n;

    scanf("%lld%lld", &a, &n);
    descomp_prim(n);
    MOD=n;
    printf("%lld\n", exp_by_squaring(a, phi_n-1)%MOD);

    return 0;
}