#include <bits/stdc++.h>

using namespace std;

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

long long N, A, phi;

long long lgput(long long x, long long n){
    long long ans = 1;
    for(int i = 0; i <= 32; i++){
        if(n & (1LL << i))
            ans = ans * x % N;
        x = x * x % N;
    }
    return ans;
}

void fact(long long x){
    int cnt = 0;
    phi = 1;
    for(int i = 2; i * i <= x; i++){
        cnt = 0;
        while(x % i == 0){
            cnt++;
            x /= i;
        }
        if(cnt > 0)
            phi = phi * lgput(i, cnt - 1) % N * (i - 1) % N;
    }
    if(x > 1)
        phi = phi * (x - 1) % N;
}

int main(){

    fin >> A >> N;
    fact(N);
    fout << lgput(A, phi - 1);

}