#include <iostream>
#include <fstream>

using namespace std;

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

int prim(int n)
{
    if(n<2)
        return 0;
    if(n%2==0 && n>2)
        return 0;
    for(int d=3;d*d<=n;d+=2)
        if(n%d==0)
            return 0;
    return 1;
}

long long P(int a, int n)
{
    long long p=1;
    while(n)
    {
        if(n%2==1)
            p=p*a;
        a=a*a;
        n/=2;
    }
    return p;
}

int Phi(int n)
{
    int r=n, d=2;
    while(n>1)
    {
        if(n%d==0)
        {
            r=r/d*(d-1);
            while(n%d==0)
                n/=d;
        }
        d++;
        if(d*d>n)
            d=n;
    }
    return r;
}

int main()
{
    int a, n;
    long long x;
    fin >> a >> n;
    // Inversul moduelar a lui a
    if(prim(n))
        x=P(a,n-1);
    else
        x = P(a,Phi(n)-1);
    fout << x%n;
    return 0;
}