#include <bits/stdc++.h>
using namespace std;
ifstream fin ("inversmodular.in");
ofstream fout ("inversmodular.out");
int a, n;
int main()
{
    int d, fi, aux , s;
    /// A ^ (fi(n) - 1) - inversul modular al lui A
    /// fi(n) - nr de numere <= n si prime cu n
    fin >> a >> n;
    aux = n;
    fi = aux;
    d = 2;
    if(aux % 2 == 0)
    {
        fi = (fi / d) * (d - 1);
        while(fi % d == 0)
            fi /= d;
    }
    d++;
    while(1LL * d * d <= aux && aux >= 1)
    {
        if(aux % d == 0)
        {
            fi = (fi / d) * (d - 1);
            while(fi % d == 0)
                fi /= d;
        }
        d += 2;
    }
    if(aux > 1)
        fi = (fi / aux) * (aux - 1);
    fi--;
    s = 1;
    while(fi > 0)
    {
        if(fi & 1)
            s = 1LL * s * a % n;
        fi /= 2;
        a = 1LL * a * a % n;
    }
    fout << s << "\n";
    fin.close();
    fout.close();
    return 0;
}