#include <cstdio>
        #include <cmath>
        using namespace std;
        bool prim (long long int x)
        {
            int i;
            for (i=2; i*i<=x; i++)
                if (x%i==0) return false; return true;
        }
        int main()
        {
            long long int a, n, i;
            freopen("inversmodular.in","r",stdin);
            freopen("inversmodular.out","w",stdout);
            scanf("%lld%lld",&a,&n);
            float k=log2(n);
            if (prim(n))
            {
                long long int x=a;
                for (i=1; i<=k; i++)
                {
                    x*=x;
                    x%=n;
                }
                int p=(n-2)-pow(2,(i-1)*1.0);
                for (i=1; i<=p; i++)
                {
                    x*=a;
                    x%=n;
                }
                printf("%lld",x);
            }
            else printf("-1");
            fclose(stdin);
            fclose(stdout);
            return 0;
        }