#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;

int a,b;
int mod;

FILE *fin,*fout;

int pow2(int num,int p)
{
    int sol=1;
    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;
}

int phi(int num)
{
    int val=num;
    int sol=num;
    bool ePrim=true;
    for(int i=2; i*i<=val; i++)
    {
        if(num%i==0)
        {
            ePrim=false;
            sol=sol*(i-1)/i;
            while(num%i==0)
            {
                num/=i;
            }
        }
    }
    if(ePrim)
    {
        return val-1;
    }
    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,"%d %d",&a,&b);
    mod=b;//trebuie sa iau restul la impartirea cu b
    int sol=inv_mod(a,b);
    fprintf(fout,"%d",sol);
    return 0;
}