#include <iostream>
#include <fstream>
#define LL long long int
using namespace std;

LL N,A;

int main(){
    ifstream in("inversmodular.in");
    ofstream out("inversmodular.out");
    in >> A >> N;

    int i,p=N-2,res=1;
    for (i=0; p; i++){
        if (p&(1<<i)){
            res=(res*A)%N;
            p-=(1<<i);
        }

        A=(A*A)%N;
    }

    out << res;
    return 0;
}