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

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

long long a, n, idk = 1, d = 2, p, 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;
}

int main(){

    fin >> a >> n;
    mod = n;
    euler(n);
    fout << exp_rap(a, idk - 1);
}