#include <bits/stdc++.h>
using namespace std;

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

typedef long long int lint;
lint A, N;

int main(){
    fin >> A >> N;
    // calculam A la puterea N-2
    lint y = N-2, rez = 1;
    while(y > 0){
        if(y%2 != 0){
            rez = rez * A % N;
            y--;
        }
        else{
            A = A * A % N;
            y /= 2;
        }
    }
    fout << rez;
    
    fin.close();
    fout.close();
    return 0;
}