#include <bits/stdc++.h>

using namespace std;
long long c,a,p,n,nr,i;
void euler()
{
    nr=0;
    for( i=1; i<n; i++)
    {
        c=__gcd(i,n);
        if(c==1) nr++;
    }
    nr--;
    p=a;
    a=1;
    while(nr)
    {
        if(nr%2==1)
        {
            a=a*p;
            a=a%n;
        }
        p=p*p;
        p=p%n;

        nr=nr/2;

    }
}
int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    scanf("%lld%lld",&a,&n);
    euler();
    printf("%lld",a%n);
    return 0;
}