#include <bits/stdc++.h>

using namespace std;

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

int a, n;

int phi (int n) {
    int rez=n;
    int d=2;
    while (n>1) {
        if (n%d==0) {
            rez=rez*(d-1)/d;
            while (n%d==0)
                n/=d;
        }
        d++;
        if (d*d>n)
            d=n;
    }
    /*if (n!=1)
        rez=rez(n-1)/n;*/
    return rez;
}

int exp (int a, int b) {
    int p=1;
    while (b) {
        if (b%2==1) {
            p*=a*1LL;
            p%=n;
        }
        a*=a*1LL;
        a%=n;
        b/=2;
    }
    return p;
}

int main() {
    fin >> a >> n;
    fout << exp(a,phi(n)-1)%n;
}