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

int prim (int n)
{
    if (n%2==0)
        return 0;
    else
        for (int i=3 ; i*i<=n ; i++)
        if (n%i==0)
        return 0;
        return 1;
}
long long a,n,MOD;
long long ridicare (long long b,long long e)
{
    long long 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;
}
long long Euler (int x)
{
    int cx=x,div=2,rez=x;
    while (cx!=1)
    {
        int ok1=0;
        while (cx%div==0)
        {
            cx/=div;
            ok1=1;
        }
        if (ok1==1)
        {
            rez=rez*(div-1);
        rez/=div;
        }

        if (div==2)
            div=3;
        else
            div+=2;
    }
    return rez;
}
int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    cin>>a>>n;
    MOD=n;
   int ok=prim(n);
    if (ok==1)
    {
        cout<<ridicare (a,n-2);
    }
    else
    {
        int phi = Euler(n);
        cout<<ridicare (a,phi-1);
    }
    return 0;
}