#include <iostream>
#include <fstream>
using namespace std;
ifstream fin ("inversmodular.in");
ofstream fout ("inversmodular.out");
long long int a, N, fi;

long long int exp_log(long long int x, long long int y);
int Phi(long long int n);

int main()
{
    fin>>a>>N;
    fi=Phi(N);
    fout<<exp_log(a,fi-1);
    return 0;
}

int Phi(long long int n)
{int d;
 long long int fi=1;
 for(d=2;d*d<=n;d++)
    {if(n%d==0)
       {while(n%d==0)
            {fi*=d;
             n/=d;
            }
        fi/=d;
        fi*=(d-1);
       }
    }
 if(n>1)
    fi*=(n-1);
 return fi;
}

long long int exp_log(long long int x, long long int y)
{long long int p;
 if(y==0)
    return 1;
    else
    if(y%2==1)
       return (x*exp_log(x,y-1))%N;
 //y%2==0
 p=exp_log(x,y/2);
 return (p*p)%N;
}