#include <bits/stdc++.h>

using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

long long a, n, nr, x;
long long fi(long long n)
{
    long long d=2, nr=1;
    while(d*d<=n)
    {
        if(n%d==0)
        {
            long long z=d-1;
            while(n%d==0)
            {
                z*=d;
                n/=d;
            }
            z/=d;
            nr*=z;
        }
        d++;
    }
    if(n>1)
        nr*=(n-1);
    return nr;
}

long long putere(long long a, long long x)
{
    if(x==0)
        return 1;
    if(x%2==0)
        return putere(a*a%n, x/2);
    return a * putere(a, x-1)%n;
}

int main()
{
    fin>>a>>n;
    nr = fi(n);
    x = putere(a, nr-1);
    fout << x;
    return 0;
}