#include <bits/stdc++.h>

using namespace std;

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

long long a, n;

static inline long long phi (long long n) {
    long long rez=n;
    long long 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;
}

static inline long long exp (long long a, long long b) {
    long long 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;
}