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

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

long long 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;
    }
}

long long exp_rap(int a, int n){

    long long p = 1;
    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;
    }

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