#include <iostream>
#include <fstream>
#define ll long long

using namespace std;

ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

ll A,N;

void citire()
{
    fin>>A>>N;
}

ll putere(ll x,ll n)
{
    ll a;
    if(!n) return 1;
    if(n==1) return x;
    a=putere(x,n/2);
    if(n%2==0) return (a*a)%N;
    else return (x*(a*a)%N)%N;
}

int main()
{
    citire();
    if(putere(A,N-2)<0) fout<<putere(A,N-2)+N;
    else fout<<putere(A,N-2);
    return 0;
}