#include <iostream>
#include <fstream>
using namespace std;
ifstream in("inversmodular.in");
ofstream out("inversmodular.out");
int n;

int lgput(int a, int b)
{
    if(b == 0)
        return 1;
    int aux = lgput(a, b / 2) % n;
    long long x = (aux * aux) % n;
    if(b % 2 == 0)
        return x % n;
    return x * a % n;
}

int phi()
{
    int aux = n;
    long long ret = aux;
    for(int i = 2; i * i <= aux; i++)
    {
        if(aux % i == 0)
            ret = ret * (i - 1) / i;
        while(aux % i == 0)
            aux = aux / i;
    }
    if(aux > 1)
        ret = ret * (aux - 1) / aux;
    return (int)ret;
}

int main()
{
    int a;
    in >> a >> n;
    out << lgput(a, phi() - 1);
    return 0;
}