#include <fstream>
#include <string.h>
using namespace std;

int ciur(int x)
{
    int nr=0;
    bool fr[x+5];
    memset(fr, 1, x+4);
    for(int i=2; i<x+1; i++)
    {
         if(fr[i]==1)
         {
             nr++;
             for(int j=i*2; j<x+1; j+=i)
                  fr[j]=0;
         }
    }
    return nr;
}

int alap(int x, int y)
{
     int sol=1;
     for(int i=0; (1<<i)<=y; i++)

    {

        if (((1<<i)&y)>0)

            sol=(sol*x);

        x=x*x;

    }
    return sol;
}

int main()
{
     ifstream f("inversmodular.in");
     ofstream g("inversmodular.out");
     int n, a, phi;

     f>>a>>n; phi=ciur(n-1);
     g<<alap(a, phi)%n;
     return 0;
}