#include <bits/stdc++.h>
#define int long long
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
int n, k;
int lgput(int base, int exp)
{
    int ans = 1, aux = base;
    for(int i = 1; i <= exp; i *= 2)
    {
        if(exp & i)
        {
            ans *= aux;
            ans %= k;
        }
        aux *= aux;
        aux %= k;
    }
    return ans;
}

int pi(int n)
{
    int ans = n;
    int nn = n;
    if(nn % 2 == 0)
    {
        ans /= 2;
        while(nn % 2 == 0)
        {
            nn /= 2;
        }
    }
    for(int i = 3; i * i <= n; i ++)
    {
        if(nn % i == 0)
        {
            ans = ans * (i-1);
            ans /= i;
            while(nn % i == 0)
                nn /= i;
        }
    }
    if(nn != 1)
    {
        ans = ans * (nn - 1);
        ans /= nn;
    }
    return ans;
}
int32_t main()
{
    fin >> n >> k;

    fout << lgput(n, pi(k) - 1);

    return 0;
}