#include <fstream>

using namespace std;

int Fi(int n)
      {
          int d,fi;
          fi=n;
          d=2;
          while(n>1 && d*d<=n)
            {
                if(n%d==0)
                {
                    fi=(fi/d)*(d-1);
                    while(n%d==0)
                      n=n/d;
                }
                 d++;
            }
                 if (n>1)
                     fi=fi/n*(n-1);
            return fi;
        }
        int putere(int a,int n,int Modulo)
          {
              int p,prod;
              prod=1;
              while(n>0)
              {
                  if(n%2==1)
                  {
                      prod=(1LL*prod*a)%Modulo;
                      p--;
                  }
                  n=n/2;
                  a=(1LL*a*a)%Modulo;

              }
              return prod;
          }
int main()
{
    ifstream fin("inversmodular.in");
    ofstream fout("inversmodular.out");
    int n,fi,prod,a;
    fin>>a>>n;
    fi=Fi(n)-1;
    prod=putere(a,fi,n);
    fout<<prod<<"\n";
    fin.close();
    fout.close();
    return 0;
}