#include <iostream>
#include <fstream>
#include <math.h>

using namespace std;

long N;

long Euler(long N)
{
    if (N == 2 ) return 1;
    int d=2,p = N, B=N,nr =0;
    while ( d <= sqrt(N) && B != 1)
    {
          if ( B % d == 0) 
              { nr++;
                p = p* (d-1) /d;
                while ( B % d == 0 )
                B /= d;
                }
          if (d == 2 ) d++;
          else d+=2;          
    }
    if ( nr == 0) return N-1;
}

long power(long A,int fi)
{
    if (fi == 1) return A % N;
    else if ( fi % 2 ==0) return power((A*A) % N, fi/2 );
         else return (A * power((A*A) % N, (fi -1)/2)) %N;
}

int main()
{
    ifstream in("inversmodular.in");
    ofstream out("inversmodular.out");
    long A;
    in>>A>>N;
    in.close();
    long fi;
    fi = Euler (N) -1;
    out<<power(A, fi);
    out.close();
    return 0;
}