#include <bits/stdc++.h>
using namespace std;

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

int a, n, idk = 1, d = 2, p;
int mod;

/*void euler(long long n){

    while(n > 1){
        p = 0;
        while(n % d == 0)
            n /= d, p++;
        
        if(p)
            idk = idk * pow(d, p - 1) * (d - 1);
        d++;
        if(d * d > n)
            d = n;
    }
}*/

int phi(int n){
    int answer = n;
    for(int i=2; i<=n/i; i++)
        if(n % i == 0){
            answer -= answer / i;
            while(n % i == 0)
                n /= i;
        }
    if(n != 1)
        answer -= answer / n;
    return answer;
}

int exp_rap(int a, int n){

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

    return p;
}

bool prim(int x){

    if(x == 0 || x == 1 || (x % 2 == 0 && x != 2))
        return 0;
    for(int d = 3; d * d <= x; d += 2)
        if(x % d == 0)
            return 0;
    
    return 1;
}

int main(){

    fin >> a >> n;
    mod = n;

    /*if(prim(n)){
        fout << exp_rap(a, n - 2);
        return 0;
    }*/

    idk = phi(n);
    fout << exp_rap(a, idk - 1);
}