#include <bits/stdc++.h>
#define prim 1999999973
#define LL long long

using namespace std;

ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

LL lgput(LL a, LL b, LL n_prim)
{
    LL s=1;
    for(LL p=1; p<=b; p<<=1)
    {
        if(p&b)
            s=(s*a)%n_prim;
        a=(a*a)%n_prim;
    }
    return s;
}

int cmmdc(int a, int b)
{
    int r = a%b;
    while(r!=0)
    {
        a = b;
        b = r;
        r = a%b;
    }
    return b;
}

int ciur(int n)
{
    if(n==1) return 0;
    bitset<2000001> b;
    int nr = 1;
    for(int i=4; i<=n; i+=2)
        b[i] = 1;
    for(int i=3; i<=n; i+=2)
    {
        if(!b[i])
        {
            for(int k=2; i*k<=n; k++)
                b[i*k] = 1;
            nr++;
        }
    }
    return nr;
}

LL phi(LL a)
{
    LL nr = a;
    for(LL i=2; i*i<=a; ++i)
    {
        if(a%i == 0)
        {
            while(a%i == 0) a/=i;
            nr = (nr/i)*(i-1);
        }
    }
    if(a!=1) nr=(nr/a)*(a-1);
    return nr;
}

LL InversModular(int n, int n_prim)
{
    return lgput(n, phi(n)-1, n_prim);
}

int main()
{
    LL a, n;
    fin >> a >> n;
    fout<<lgput(a, phi(n)-1, n);
    return 0;
}