#include <iostream>
#include <bits/stdc++.h>
using namespace std;

bool ciur[1000000000];
int ok=0;
void Ciur (int n)
{
    for (int i=2 ; i<=n ; i++)
         if (ciur[i]==0)
    {
        if (n%i==0 && i!=1 && i!=n)
        ok=1;
        for (int j=2 ; j*i<=n ; j++)
            ciur[j*i]=1;
    }


}
int a,n,MOD;
int ridicare (int b,int e)
{
    int rez=1;
    while (e!=0)
    {
        if (e%2==0)
        {
            b=b*b;
            b=b%MOD;
            e/=2;
        }
        else
        {
            rez=b*rez;
            rez=rez%MOD;
            e--;
        }

    }
    return rez;
}
int Euler (int x)
{
    int primi[x/2+1];
    int cont=0;
    for (int i=1 ; i<=x/2 ; i++)
    {
        if (ciur[i]==0)
        {
            cont++;
            primi[cont]=i;
        }
    }
    int numarator=x ;
    for (int i=2 ; i<=cont ; i++)
        if (x%primi[i]==0)
    {
        numarator*=(primi[i]-1);
        numarator/=primi[i];
    }
    return numarator;
}
int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    cin>>a>>n;
    Ciur(n);
    MOD=n;
    if (ok==0)
    {
        cout<<ridicare (a,n-2);
    }
    else
    {
        int phi = Euler(n);
        cout<<ridicare (a,phi-1);
    }
    return 0;
}