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

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

int a, N;

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

int euler(int n)
{
    int r = n;
    for(int 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;
    int putere = pow(a, euler(N) - 1);
    fout << putere % N;
}