#include <bits/stdc++.h>
#define N 2000000000
using namespace std;
int exp(long long a, long long b, int n){
    long long p = 1;
    while(b != 0){
        if(b % 2 == 1){
            p *= a;
            p %= n;
        }
        a *= a;
        a %= n;
        b /= 2;
    }
    return p;
}

int main()
{
    FILE *in, *out;
    in = fopen("inversmodular.in", "r");
    out = fopen("inversmodular.out", "w");
    long long a, d = 2, e, n, cp;
    fscanf(in, "%d%d",&a,&n);
    e = n;
    cp = n;
    while(d * d <= n){
        if(n % d == 0){
            e *= d - 1;
            e /= d;
        }
        while(n % d == 0){
            n /= d;
        }
        d++;
    }
    if (n != 1) {
        e *= n - 1;
        e /= n;
    }
    fprintf(out, "%d",exp(a, e - 1, cp));
    return 0;
}