#include <bits/stdc++.h>

using namespace std;
ifstream fin ("inversmodular.in");
ofstream fout ("inversmodular.out");
int a,n,E=1,mod;

int Putere(int A , int n)
{
    int P = 1;
    for(int k = 1 ; k <= n ; k <<= 1)
    {
        if((n & k))
            P =1ll* P * A % mod;
        A = 1ll* A * A % mod ;
    }
    return P % mod;
}
int Putere2(int A , int n)
{
    int P = 1;
    for(int k = 1 ; k <= n ; k <<= 1)
    {
        if((n & k))
            P =1ll* P * A;
        A = 1ll* A * A;
    }
    return P;
}
void euler(int n){
    int d=2;
    while(n>1)
    {
        int p=0;
        while(n%d==0)
        {
            n=n/d;
            p++;
        }
    if(p)
        E=E*Putere2(d,p-1)*(d-1);
    d++;
    if(d*d>n)
        d=n;
    }
}
int main()
{
    fin>>a>>n;
    mod=n;
    euler(n);
    fout<<Putere(a,E-1);
    return 0;
}