#include <bits/stdc++.h>

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

long long a,n;

long long raisePower(long long nr, long long p)
{
    int sol=1;
    for(int i=0;(1<<i)<=p;++i)
    {
        if(((1<<i) & p)>0)
            sol=(sol*nr)%n;

        nr=(nr*nr)%n;
    }
    return sol;
}

int main()
{
    fin>>a>>n;

    int phi=0;
    for(int i=1;i<=ceil(sqrt(n));++i)
    {
        if(n%i || i==1)
            ++phi;

        if(n%(n-i))
            ++phi;

    }

    fout<<raisePower(a,phi-1)%n;

    return 0;
}