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

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

int a, b;
int exp(int a, int n)
{
    long long p = 1;
    while(n)
    {
        if(n & 1)
        p = p * 1LL * a%b;
        a = 1LL * a * a % b;
        n>>=1;
    }
    return p;
}

int phi(int n)
{
    int ans = n;
    for(int p = 2;n > 1 && p * p <= n; p++)
    {
        if(n % p == 0)
        {
            ans -= ans / p;
            while(n % p == 0)
            n/=p;
        }
    }
    if(n > 1)
        ans -= ans / n;
    return ans;
}

int main()
{
    fin >> a >> b;
    fout << exp(a,phi(b) - 1);
    fin.close();
    fout.close();
    return 0;
}