#include <fstream>

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

long long nr, a, rez, b, put;

long long calc(long long n){
    long long cur = n;
    for(int i = 2; i * i <= n; i++){
        if(n % i == 0){
            while(!(n/i)) n/=i;
            cur -= cur/i;
        }
    }

    if(n != 1) cur -= cur/n;
    return cur;
}

int main()
{
    fin >> a >> b;
    put = calc(b) - 1;
    long long rez = 1;
    for(int i = 1; i <= put; i <<= 1){
        if(i & put){
            rez = rez * a % b;
        }

        a = a * a % b;
    }

    fout << rez;

    return 0;
}