#include <bits/stdc++.h>

using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
int y,n;
void phi(int a)
{
    int p=a,s=a,x;
    for(int i=2;i*i<=a;++i)
    {
        if(a%i==0)
        {
            while(a%i==0)a/=i;
            p=p/i*(i-1);
        }
    }
    if(a>1)p=p/a*(n-1);
    x=p-1;
    p=y;
    y=1;
    while(x)
    {
        if(x%2)y*=p,y%=s;
        p=(p*p)%s;
        x/=2;
    }
}
int main()
{
    fin>>y>>n;
    phi(n);
    fout <<y%n << '\n';
    return 0;
}