# include <cstdio>
# include <algorithm>
# define i64 long long
using namespace std;
i64 power(i64 x,i64 y,i64 mod)
{
    if (!y) return  1;
    i64 p(1),putere(x);
    while (p*2<=y)
    {
        p*=2;
        putere=(putere*putere)%mod; 
    } 
    return (putere*power(x,y-p,mod))%mod;
}
i64 euler(i64 x)
{
    i64 n=x;
    for (i64 i=2;i*i<=x;++i)
         if (!(x%i))
           {
                    while (!(x%i)) x/=i;
                    n=(n/i)*(i-1);
           }
    if (x!=1) n=(n/x)*(x-1);
    return (n);       
}
int main(void)
{
    int n,a;
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    scanf("%d%d",&a,&n);
    printf("%i\n",power(a,euler(n)-1,n));
    return 0;    
}