#include <bits/stdc++.h>

using namespace std;

ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

int a,b,mod;

int Lgput(int x,int n)
{
    int s=1;
    while(n>0)
    {
        if(n%2==1)s=1LL*s*x%mod;
        x=1LL*x*x%mod;
        n/=2;
    }
    return s;
}

int Phi()
{
    int p,d;
    p=b;

    if(b%2==0)
    {
        p=p/2;
        while(b%2==0)
            b/=2;
    }
    d=3;

    while(1LL*d*d<=b && b>1)
    {
        if(b%d==0)
        {
            p = (p / d) * (d - 1);
            while(b%d==0)
                b/=d;
        }
        d+=2;
    }

    if(b>1)p = (p / b) * (b - 1);
    return p;
}

int main()
{
    fin>>a>>b;

    mod=b;
    b=Phi();

    fout<<Lgput(a,b-1);
    fin.close();
    fout.close();
    return 0;
}