#include <iostream>
#include <fstream>
using namespace std;

ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

long long a , n;
long long mod;

long long exp ( int n , int p )
{
    if ( p == 0 )
        return 1;
    else if ( p%2 == 1) return (n%mod * (exp((n%mod*n%mod)%mod,p/2)) %mod ) %mod;
        else return exp((n%mod*n%mod)%mod,p/2)%mod;
}

int main()
{
    f >> a >> n;
    mod = n;
    g << exp(a,n-2);
    return 0;
}