#include <fstream>

using namespace std;

int Fi(int n)
{
    int d,fi;
    fi=n;
    d=2;
    while(n>1 && d*d<=n)
    {
        if(n%d==0)
        {
            fi=(fi/d)*(d-1);
            while(n%d==0)
                n=n/d;
        }
        d++;
    }
    if(n>1)
      fi=fi/n*(n-1);
    return fi;
}

int putere(int a, int n, int Modulo)
{
    int prod;
    prod = 1;
    while(n>0)
    {
        if(n%2==1)
        {
            prod=(1LL*prod*a)%Modulo;
            n--;
        }
        n=n/2;
        a=(1LL*a*a)%Modulo;
    }
    return prod;
}

int main()
{
    ifstream fin ("inversmodular.in");
    ofstream fout ("inversmodular.out");
    int n,fi,prod,a;
    fin >> a >> n;
    fi=Fi(n)-1;
    prod = putere(a, fi, n); /// a^fi % n
    fout<<prod << "\n";
    fout.close();
    fin.close();
    return 0;
}