#include<iostream>
#include<fstream>
#include<algorithm>
#include<cmath>
using namespace std;
int v[45000],p[45000];
int x,fi=1,a,n;

int putlog (int nr,int exp,int mod)
{
        if (exp==0)
        {
            return 1;
        }
        if (exp==1)
        {
            return nr%mod;
        }
        return ((putlog(nr,exp/2,mod)%mod)*(putlog(nr,exp/2+exp%2,mod)%mod))%mod;
}

int main()
{
    ifstream fin ("inversmodular.in");
    ofstream fout ("inversmodular.out");
    for(int i=2; i<=45000; i++)
    {
        if(v[i]==0)
        {
            for(long long int j=i*i; j<=45000; j+=i)
            {
                v[j]=1;
            }
            p[++x]=i;
        }
    }
    int n2;
    fin>>a>>n;
    n2=n;
    int ind=0;
    while(n!=1 && ind<=x)
    {
        ind++;
        int prim=p[ind],exp=0;
        while (n%prim==0)
        {
            n/=prim;
            exp++;
        }
        if (exp)
        {
            fi=fi*(prim-1)*putlog(prim,(exp-1),n2);
        }
    }
    if (n2==n)
    {
        fi=n-1;
    }
    fout<<putlog(a,fi-1,n2);
    return 0;
}