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

std::ifstream fin("inversmodular.in");
std::ofstream fout("inversmodular.out");

long long a, N;

long long power(long long n, long long pow)
{
    if(pow == 0) return 1;
    if(pow % 2)  return (power(n * n % N, pow / 2) * n) % N;
    return (power(n * n % N, pow / 2))%N;
}

long long euler(int n)
{
    long long r = n;
    for(long long i = 2; i * i <= n; i++)
    {
        if(n % i == 0)
        {
            while(n % i == 0) n /= i;
            r = (r / i) * (i - 1);
        }
    }
    if(n != 1) r = r / n * (n - 1);
    return r;
}

int main()
{
    fin >> a >> N;
    long long putere = power(a, euler(N) - 1);
    fout << putere % N;
}