#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 == 1)  return (n * power(n * n % N, pow / 2))% 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;
}*/

long long euler(long long n)
{
    long long r=n,d=2;
    while(n>1)
    {
        if(n%d==0)
        {
            r = r / d * (d - 1);
            while(n%d==0)
                n/=d;
        }
        d++;
        if(d*d>n)
            d=n;
    }
    return r;
}

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