#include <bits/stdc++.h>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

long long a, n, fi, x, MOD;

long long phi(int n) {
    long long rez = n;
    int d=2, e;
    while(d*d<=n) {
        e = 0;
        while(n%d == 0) {
            e++;
            n/=d;
        }
        if(e > 1)
            rez = rez/d*(d-1);
        d++;
    }
    if(n > 1)
        rez  =rez/n * (n-1);
    return rez;
}
long long putere(long long b, long long e) {
    if(e == 0)
        return 1;
    if(e%2 == 0)
        return putere(b*b%MOD, e/2);
    return (b*putere(b*b%MOD, e/2))%MOD;
}
int main()
{
    fin >> a >> n;
    MOD = n;
    fi = phi(n);
    x = putere(a, fi-1)%MOD;
    fout << x;
    return 0;
}