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

using namespace std;

long long N;

long long Euler()
{
    if (N == 2 ) return 1;
    int d=2;
    long long p = N, B=N;
    while ( d <= sqrt(B))
    {
          if ( B % d == 0) 
              { 
                p = (p /d )* (d-1);
                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 == 0 ) return 1;
    if (fi == 1) return A % N ;
    else if ( fi % 2 ==0) return (power((A*A)%N, fi/2 ) % N);
         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;
}