#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

LL ridicare(LL baza, int exp, int n)
{
    LL ans = 1;

    while(exp)
    {
        if(exp % 2)
            ans = ans * baza % n;

        baza = baza * baza % n;
        exp /= 2;
    }

    return ans;
}

int phi(int n)
{
    int ans = n;

    int div = 2;

    while(div * div <= n)
    {
        int cnt = 0;

        if(n % div == 0)
        {
            while(n % div == 0)
                n /= div;

            if(cnt)
                ans = ans / div * (div - 1);
        }

        div++;
    }

    if(n > 1)
        ans = ans / n * (n - 1);

    return ans;
}

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

    int a, n;

    fin >> a >> n;
    cout << phi(n);

    fout << ridicare(a, phi(n) - 1, n);

    fin.close();
    fout.close();

    return 0;
}