#include <bits/stdc++.h>
using namespace std;

/// INPUT / OUTPUT
const string problem = "inversmodular";
ifstream fin(problem + ".in");
ofstream fout(problem + ".out");

/// GLOBAL VARIABLES
const int NMAX = 1;
int a, n;

inline int euler(int x)
{
    int e = x, d = 2;
    while(d * d <= x)
    {
        if(x % d == 0)
        {
            e = e / d * (d - 1);
            while(x % d == 0)
            {
                x /= d;
            }
        }
        d++;
    }
    if(n != 1)
    {
        e = e / x * (x - 1);
    }
    return e;
}

inline int power(int x, int y, int MOD)
{
    int p = 1;
    while(y)
    {
        if(y%2)
        {
            p =(long long) p * x % MOD;
        }
        x = (long long)x * x % MOD;
        y>>=1;
    }
    return p;
}

/// SOLUTION
inline void solution()
{
    int phi = euler(n);
    fout << power(a, phi - 1, n);
}

/// READING THE INPUT
int main()
{
    ios::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);

    fin >> a >> n;

    solution();
}