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

using namespace std;

long long N;

long long Euler()
{
    if (N == 2 ) return 1;
    int d=2 ,nr =0;
    long long p = N, B=N;
    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 ( B != 1) return N-1;
    else return p;
}

long long power(long long A,long long 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 long A;
    in>>A>>N;
    in.close();
    long long fi;
    fi = Euler() -1;
    out<<(power(A, fi)%N);
    out.close();
    return 0;
}