#include <bits/stdc++.h>

using namespace std;


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

#define int long long

int a,n;

int lgput(int put)
{
    int pt = 1;
    while (put != 0)
    {
        if (put % 2 == 1)
            pt = pt * a % n;
        a = a * a % n;
        put /= 2;
    }
    return pt % n;
}

int get_fi()
{
    int p = n,nr = n;
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0)
        {
            p = p / i * (i - 1);
            while (n % i == 0)
                n /= i;
        }
    if (n != 1)
        p = p / n * (n - 1);
    n = nr;
    return p;
}

signed main()
{
    in >> a >> n;
    int put = get_fi() - 1;
    out << lgput(put);
    return 0;
}