//#include <iostream>
#include <fstream>
using namespace std;

#define ull unsigned long long

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

bool prim(ull n)
{
    if(n == 2)
        return true;

    if(n < 2 || n % 2 == 0)
        return false;

    for(ull d=3; d*d<=n; d++)
    {
        if(n % d == 0)
            return false;
    }

    return true;
}

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

int nr_prim_cu_n(ull n)
{
    int nr = 0;

    for(ull i = 1; i < n; i++)
        if(gcd(i, n) == 1)
            nr++;

    return nr;
}

ull power(ull a, ull n, const ull mod)
{
    ull p = 1;
    while(n)
    {
        if(n % 2 == 1)
            p *= a, p %= mod;

        a *= a; a %= mod;
        n /= 2;
    }

    return p % mod;
}

int main()
{

    ull a, x, n, i, p = 1;
    cin>>a>>n;

    if(prim(n)) p = n - 1;
    else p = nr_prim_cu_n(n);

    x = power(a, p-1, n);

    cout<<x;

    return 0;
}