#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstring>
#include <climits>
#include <unordered_map>

#define NMAX 2000003

using namespace std;

long long int a,b;
int mod;

FILE *fin,*fout;

long long int pow2(long long int num,int p)
{
    long long int sol=1;
    long long int inter=num;
    while(p>0)
    {
        if(p%2==1)
        {
            sol=1ll*sol*inter%mod;
            p--;
        }
        inter=1ll*inter*inter%mod;
        p=p/2;
    }
    return sol;
}

long long int phi(int num)
{
    
    long long int sol=num;
    for(int i=2; i*i<=num; i++)
    {
        if(num%i==0)
        {
            sol=sol*(i-1)/i;
            while(num%i==0)
            {
                num/=i;
            }
        }
    }
    if(num>1)
    {
        sol=sol*(num-1)/num;
    }
    return sol;
}

int inv_mod(int a,int b)
{
    return pow2(a,phi(b)-1);
}

int main()
{
    fin=fopen("inversmodular.in","r");
    fout=fopen("inversmodular.out","w");
    

    fscanf(fin,"%lld %lld",&a,&b);
    mod=b;//trebuie sa iau restul la impartirea cu b
    long long int sol=inv_mod(a,b);
    fprintf(fout,"%lld",sol);
    return 0;
}