#include <iostream>
#include <fstream>
using namespace std;

ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

int inversmodular(int a, int n){
    for(int i=1;i<=n-1;i++){
        if(a*i%n==1) return i;
    }
    return -1;
}

int Phi(int n){
    int d=2, nr=n;
    while(n>1){
        if(n%d==0){
            nr=nr/d*(d-1);
            while(n%d==0){
                n/=d;
            }

        }
        if(d==2) d++;
        else d+=2;
        if(d*d>n) d=n;
    }
    return nr;
}

int Putere(int A , int n)
{
    int P = 1;
    while(n)
    {
        if(n % 2 == 1)
            P = (P * A)%n;
        A = (A * A)%n;
        n /= 2;
    }
    return P;
}

int main()
{
    int a, n, phin, prod;
    f>>a>>n;
    phin=Phi(n);
    g<<Putere(a,phin-1)%n;
    return 0;
}