#include <bits/stdc++.h>
using namespace std;
ifstream fin ("inversmodular.in");
ofstream fout("inversmodular.out");
int phi,n;

void descomp(int n)
{
    int f=2,e=0;
    while (n%f==0)
        {
            n/=f;
            e=1;
        }
    if (e==1)
        phi=(n/f)*(f-1);
    for (f=3;f*f<=n;f+=2)
    {
        e=0;
        while (n%f==0)
        {
            n/=f;
            e=1;
        }
        if (e==1)
            phi=(n/f)*(f-1);
    }
    if (n!=1)
        phi=n-1;
   }

int ridica (int baza,int exp)
{
    int sol=1;
    while (exp!=0)
    {
        if (exp%2==1)
            {
                sol=sol*baza;
                sol%=n;
            }
        baza=baza*baza;
        baza%=n;
        exp/=2;
    }
    return sol;
}

int main()
{
    int  a;
    fin>>a>>n;
    phi=n;
    descomp (n);
    fout<<ridica(a,phi-1);
    return 0;
}