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

int_fast64_t putlog (int_fast64_t nr,int_fast64_t exp,int_fast64_t 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_fast64_t i=2; i<=45000; i++)
    {
        if(v[i]==0)
        {
            for(int_fast64_t j=i*i; j<=45000; j+=i)
            {
                v[j]=1;
            }
            p[++x]=i;
        }
    }
    int_fast64_t n2;
    fin>>a>>n;
    n2=n;
    int_fast64_t ind=0;
    while(n!=1 && ind<x)
    {
        ind++;
        int_fast64_t 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;
    }
    int_fast64_t x=putlog(a,fi-1,n2);
    while(x<0)
    {
        x+=n2;
    }
    fout<<x;
    return 0;
}