#include <iostream>
#include <fstream>
#define int long long
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");


long long n,MOD;

int putere(int x, int p)
{
    if (p==0)
        return 1;

    if (p%2==1)
        return x*putere(x,p-1)%MOD;

    int P=putere(x,p/2)%MOD;
    return P*P%MOD;
}

int etf(int val)
{
    int rasp=val,d=2;

    while (d*d<=val)
    {
        int p=0;
        while (val%d==0)
        {
            p++;
            val/=d;
        }

        if (p!=0)
            rasp=rasp/d*(d-1);

        d++;
    }


    if (val>1)
        rasp=rasp/val*(val-1);

    return rasp;
}

signed main()
{
    fin>>n>>MOD;
    
    fout<<putere(n,etf(MOD)-1);
    
    
    return 0;
}