#include <fstream>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
long getsd( long n)
{
    long aux = n, i;
    for( i = 2; i * i <=n; i++)
        if( n % i == 0)
        {
            while ( n %i == 0) n/= i;
            aux = (aux / i)*( i - 1);
        }
        if(  n != 1) aux = aux/n*(n-1);
        return aux;
}
int main()
{
    long long  a, n, p =1;
    long long k;
    fin >> a >> n;
    k = getsd(n) -1;
    while( k != 1)
        if( k % 2 == 0)
        {
            k /= 2;
            a = a*a%n;
        }
        else{
            p = p *a %n;
            k--;
        }
        fout << p*a%n;

    return 0;
}