#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

ifstream fin;
ofstream fout;

long long mod, a;
long long i, j;

vector <bool> prime (20000001 , true);

long long log_exp (long long base, long long power){
    long long to_return;

    if (power == 1ll) return (base%mod);

    long long aux = power % 2;
    switch (aux){
        case 0ll:
            to_return = log_exp((base%mod) * (base%mod), power/2) % mod;
            break;

        case 1ll:
            to_return = (base%mod * ((log_exp((base%mod) * (base%mod), power/2)) %mod));
            break;
    }

    return to_return;
}

long long getphi (long long number){
    long long to_return = number;
    for (i=2; i<=a/2; i++)
        if (prime[i]){
            for (j=i+i; j<=a/2; j+=i)
                prime[j] = false;

            if (!(a%i)) to_return = to_return * (i - 1) / i;
        }

    return to_return;
}


int main(void){
    fin.open("inversmodular.in");
    fin>>a>>mod;
    fin.close();

    long long exponent, result;

    exponent = getphi(a);

    result = log_exp(a, exponent);

    result %= mod;

    fout.open("inversmodular.out");
    fout<<result<<"\n";
    fout.close();

    return 0;
}