#include <iostream>
#include <fstream>

#define ll long long

using namespace std;

ll M;

ll int power(ll int n, ll int p) //computes n ^ p modulo M
{
    if(p == 0)
        return 1;

    ll int x = 1;
    while(p > 1)
    {
        if(p % 2)
        {
            x = ((x % M) * (n % M)) % M;
            p--;
        }
        n = ((n % M) * (n % M)) % M;
        p = p / 2;
    }
    
    return ((n % M) * (x % M)) % M;
}

ll phi(ll n)
{
    ll result = n;

    for(int i = 2; i * i <= n; i++)
    {
        if(n % i == 0)
        {
            while(n % i == 0)
            {
                n /= i;
            }
            result -= result / i;
        }
    }

    if(n > 1)
    {
        result -= result / n;
    }
    
    return result;
}

int main(void)
{
    ifstream fin("inversmodular.in");
    ofstream fout("inversmodular.out");
    
    ll A;
    fin >> A >> M;

    fout << power(A, phi(M) - 1) << "\n";

    fin.close();
    fout.close();
    return 0;
}