#include<bits/stdc++.h>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
int phi(int x)
{
    int euler=x,f,p;
    f=2;
    while(f*f<=x)
    {
        p=0;
        while(x%f==0)
        {
            p++;
            x=x/f;
        }
        if(p>0)
            euler=euler/f*(f-1);
        f++;
    }
    if(x>1)
        euler=euler/x*(x-1);
    return euler;
}
long long fastpowmod(int a,int b,int n)
{
    long long aa,p;
    aa=a;
    for(p=1;b;b=b>>1)
    {
        if(b&1)
            p=(p*aa)%n;
        aa=(aa*aa)%n;
    }
    return p;
}
int invers_modular(int A,int N)
{
    return fastpowmod(A,phi(N)-1,N);
}
int main()
{
    int A,N;
    fin>>A>>N;
    fout<<invers_modular(A,N);
    return 0;
}