#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
int A,N,X;




int main()
{
   int N,A,X = 1;

    fin >> N >> A;
 int P=N-2;
    while(P)
      {
        if(P%2 == 1)
          X = (1LL *X * A);
        A = (1LL * A * A) ;
        P = P / 2;
      }
      X=X%N;
    fout<<X<<"\n";
    return 0;
}