#include <iostream>
#include <fstream>
using namespace std;
ifstream in("inversmodular.in");
ofstream out("inversmodular.out");
int putere(int a, int n, int m)
{
    int p = 1;
    do
    {
        if(n % 2 != 0)
        {
            p=(long long)p*a%m;
        }
        a=(long long)a*a%m;
        n/=2;
    }
    while(n!=0);
    return p;
}
int euler(int n)
{
    int d=2,p,rez=n,x;
    while(d*d<=n)
    {
        p=0;
        while(n%d==0)
        {
            n/=d;
            p++;
        }
        if(p)
        {
            x=(d-1)/putere(d,p,2000000001);
            rez*=x;
        }
        d++;
    }
    if(rez==n)
        rez=n-1;
    else if(n and rez)
    {
        x=(n-1)/n;
        rez*=x;
    }
    return rez;
}

int main()
{
    int  a, n, x;
    in >> a >> n;
    in.close();
    x = putere(a, euler(n) - 1, n);
    out << x;
    out.close();
    return 0;
}