#include <iostream>
#include <fstream>

using namespace std;

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

int fi(int n){
    int f, d;

    f = n;
    d = 2;
    while(d * d <= n){
        if(n % d == 0){
            f /= d;
            f *= (d - 1);
            while(n % d == 0){
                n /= d;
            }
        }
        d++;
    }
    if(n != 1){
        f /= n;
        f *= (n - 1);
    }
    return f;
}
int expp(int a, int n, int mod){
    int p;

    p = 1;
    while(n > 0){
        if(n % 2 != 0){
            p = (long long)p * a % mod;
        }
        a = (long long)a * a % mod;
        n /= 2;
    }
    return p;
}

int main()
{
    int a, n, f;

    fin >> a >> n;
    f= fi(n);
    fout << expp(a, f - 1, n) << "\n";
    return 0;
}