#include<bits/stdc++.h>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

#define MOD 1999999973

long long n,a,phi;

long long phi_euler(long long nr)
{
    long long i,phii=nr;
    for(i=2; i*i<=nr; i++)
    {
        if(nr%i==0)
        {
            phii/=i;
            phii*=(i-1);
            while(nr%i==0)
                nr=nr/i;
        }
    }
    if(nr!=1)//ins ca a ramas un nr prim
    {
        phii/=nr;
        phii*=(nr-1);
    }
    return phii;
}

long long lgput(long long base,long long exp)
{
    int i;
    long long aux=base,ans=1;
    for(i=1; i<=exp; i*=2)
    {
        if(i&exp)
            ans=(ans*aux)%n;
        aux=(aux*aux)%n;
    }
    return ans;
}

int main()
{
    fin>>a>>n;
    phi=phi_euler(n);
    fout<<lgput(a,phi-1);
    return 0;
}