#include <iostream>
#include <fstream>
using namespace std;
ifstream si("inversmodular.in");
ofstream so("inversmodular.out");
long long phi(long long val) {
    long long cont=val;
    if(!(val&1)) {
        while(!(val&1))
            val>>=1;
        cont/=2;
    }
    for(int i=3; i*i<=val; i+=2) {
        if(val%i==0) {
            while(val%i==0)
                val/=i;
            cont=(cont/i)*(i-1);
        }
    }
    if(val!=1) {
        cont=(cont/val)*(val-1);
    }
    return cont;
}
int main()
{
    long long n, m;
    si>>n>>m;
    long long put=phi(m)-1;
    long long val=1;
    while(put)
    {
        if(put&1)
        {
            val=(val*n)%m;
        }
        n=(n*n)%m;
        put>>=1;
    }
    so<<val;
    return 0;
}