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