#include <bits/stdc++.h>

using namespace std;

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

long long phi(long long x)
{
    long long 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 fastpow(int a,int b)
{
    long long aa,p;
    aa=a;
    for(p=1; b; b=b>>1){
        if(b&1){
            p=p*aa;
        }
        aa=aa*aa;
    }
    return p;
}

long long fastpowmod(long long a,long long b,long long n)
{
        long long aa,p;
        aa=a%n;
        for(p=1; b; b=b>>1){
            if(b&1)
                p=(p*aa)%n;
            aa=(aa*aa)%n;
        }
        return p;
}

long long invers_modular(long long A,long long N)
{
    return fastpowmod(A,phi(N)-1,N);
}

int main()
{
    long long A,N;
    fin>>A>>N;
    fout<<invers_modular(A,N);
    return 0;
}