#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>

typedef long long ll;
typedef long double ld;

using namespace std;

const string FILENAME = "inversmodular";

/// #define int long long

#define OpenIN() freopen((FILENAME+".in").c_str(),"r",stdin)
#define OpenOUT() freopen((FILENAME+".out").c_str(),"w",stdout)
#define OpenALL() OpenIN(), OpenOUT()
#define infoarena() OpenALL()

inline int phi (int n)
{
    int res = n;

    for (int i = 2; i * i <= n; i++)
    {
        bool entr = 0;

        while (n % i == 0)
        {
            n /= i;
            entr = 1;
        }

        if (entr)
        {
            res = res / i * (i - 1);
        }
    }

    if (n > 1)
    {
        res = res / n * (n - 1);
    }

    res--;
    return res;
}

int32_t main()
{
    ios_base::sync_with_stdio (0);
    cin.tie (0), cout.tie (0);
    infoarena();
    int a, mod;
    cin >> a >> mod;
    int up = phi (mod);
    int res = 1;

    while (up)
    {
        if (up & 1)
        {
            res = res * (long long) a % mod;
        }

        a = a * (long long) a % mod;
        up >>= 1;
    }

    cout << res << "\n";
    return 0;
}
/**

**/