#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*(d-1);
            while (n%d==0)
                n/=d;
        }
        d++;
        if (d*d>n)
            d=n;
    }
    return rez;
}

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

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