#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
int cmmdc(int a, int b)
{
    int r=a%b;
    while(r)
    {
        a=b;
        b=r;
        r=a%b;
    }
    return b;
}
int main()
{
    int n, i, a, fi, rez;
    fin >> a >> n;
    a=sqrt(n);
    fi=n-1;
    for(i=2; i<n-1; i++)
        if(cmmdc(i, n)>1)  fi--;
    while(fi)
    {
        if(fi%2==0)
        {
            a=(a*a)%n;
            fi=fi/2;
        }
        else
        {
            rez=(rez*a)%n;
            fi--;
            a=(a*a)%n;
            fi=fi/2;
        }
    }
    a=(a*rez)%n;
    fout << a;
    return 0;
}