#include <fstream>

using namespace std;

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


bool prim(int n){
    if(n < 2) return 0;
    if(n == 2) return 1;
    if(n % 2 == 0) return 0;
    for(int i = 3; i*i <= n; i += 2){
        if(n % i == 0){
            return 0;
        }
    }

    return 1;
}

int put(int a, int b, int mod){
    int ans = 1;
    while(b){
        if(b % 2 == 0){
            b /= 2;
            a = 1LL*a*a % mod;
        }
        else {
            ans = 1LL*ans * a % mod;
            --b;
        }
    }

    return ans;
}

int fi(int n){
    int ans = n;
    int cop = n;
    if(cop % 2 == 0){
        ans /= 2;
        while(cop % 2 == 0) cop /= 2;
    }

    int d = 3;
    while(d*d <= cop){
        if(cop % d == 0){
            ans /= d;
            ans *= d - 1;
            while(cop % d == 0) cop /= d;
        }
        d += 2;
    }

    ans /= cop;
    if(cop != 1) ans *= cop - 1;

    return ans;
}


int main()
{
    int a, n;
    in >> a >> n;

    out << put(a, fi(n)-1, n);
    return 0;
}