#include <bits/stdc++.h>
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define int long long
using namespace std;
const string TASK("inversmodular");
ifstream fin(TASK + ".in");
ofstream fout(TASK + ".out");
#define cin fin
#define cout fout

const int N = 1e5 + 9;

int n, m;

int PtLg(int base, int exp)
{
    int ret = 1;
    for(; exp; exp >>= 1, base = base * base % m)
        if(exp & 1)
            ret = ret * base % m;
    return ret;
}

int get_phi(int x)
{
    int ret = 1;
    for(int d = 2; x != 1;)
    {
        int nr = 1;
        while(x % d == 0)
        {
            x /= d;
            nr *= d;
        }

        if(nr > 1)ret *= nr - nr / d;

        if(d * d > x)d = x;
        else ++ d;
    }
    return ret;
}

signed main()
{
    cin >> n >> m;

    cout << PtLg(n, get_phi(m) - 1);
    return 0;
}