#include <bits/stdc++.h>
using namespace std;
int a,n;
int phi(int x);
int expl(int x,int y);
int main()
{
    ifstream in("inversmodular.in");
    ofstream out("inversmodular.out");
    in>>a>>n;
    out<<expl(a,phi(n)-1)%n<<"\n";
}
int phi(int x)
{int i=2,s=1,c;
    while (1LL*i*i<=x)
    {
        c=1;
        while (x%i==0)
        {
            x/=i;
            c=1LL*c*i%n;
        }
        s=1LL*s*(c-(c/i))%n;
        i++;
    }
    if (x>1)
      s=1LL*s*(x-1)%n;
    return s;
}
int expl(int x,int y)
{int fin=1;
    while (y>0)
    {
        if (y%2==1)
            fin=1LL*fin*x%n;
        x=1LL*x*x%n;
        y/=2;
    }
    return fin;
}